text:
\section{Concentration of the overlap}\label{app:concentration_overlap}
One important result in order to prove Propositions~\ref{prop:upperbound_mutual_info} and \ref{prop:lowerbound_mutual_info} is the concentration of the scalar overlap $Q$ around its expectation $\E \langle Q \rangle_{t,R}$ as long as we integrate over $R$ in a bounded subset of $(0,+\infty)$.
Remember that the angular brackets $\langle - \rangle_{t,R}$ denote the expectation with respect to the posterior distribution \eqref{posterior_H_t_R}.
\begin{proposition}[Concentration of the overlap around its expectation]\label{prop:concentration_overlap}
Suppose that \ref{hyp:S_bounded_support} and \ref{hyp:varphi} hold.
Let $M >0$.
For $n$ large enough, there exists a constant $C$, which depends only on $\Vert \varphi \Vert_{\infty}$, $\Vert \varphi' \Vert_{\infty}$, $\Vert \varphi'' \Vert_{\infty}$, $M_S$, $\lambda$ and $M$, such that $\forall (a,b) \in (0,M)^2: a < \min\{1,b\}$, $\forall \delta \in (0,a)$, $\forall t \in [0,1]$:
\begin{equation}\label{eq:concentration_overlap}
\int_{a}^{b} \E\,\big\langle \big(Q -\E\,\langle Q \rangle_{t,R}\,\big)^2\,\big\rangle_{t,R}\, dR
\leq C\bigg(\frac{1}{\delta^2 n} - \frac{\ln(a)}{n} + \frac{\delta}{a-\delta}\bigg)\;.
\end{equation}
\end{proposition}

The concentration of the scalar overlap around its expectation will follow from the concentration of the quantity:
\begin{equation}\label{def_L}
\cL
= \frac{1}{n}\sum_{j=1}^{n} \frac{\lambda}{4} x_j^2 - \frac{\lambda}{2}\, x_j X_j - \frac{1}{2}\sqrt{\frac{\lambda}{2 R}}\, x_j\widetilde{Z}_j \:.
\end{equation}

\begin{lemma}[Link between the fluctuations of \texorpdfstring{$\cL$}{L} and \texorpdfstring{$Q$}{Q}]\label{lemma:computation_E<L>_and_others}\\
Assume $\varphi: \R \to \R$ is continuous and bounded. For all $(t,R) \in [0,1] \times (0, +\infty)$:
\begin{align}
\E\,\langle \cL \rangle_{t,R} &=  -\frac{\lambda}{4} \E\,\langle Q \rangle_{t,R} \;;\label{formula_E<L>}\\
\frac{\lambda}{4}\E\,\langle (Q - \langle Q \rangle_{t,R})^2 \rangle_{t,R}
&\leq \frac{\Vert \varphi \Vert_{\infty}^2}{\sqrt{2}}\sqrt{\E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	-\frac{1}{n}\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R}} \;\:;\label{upperbound_fluctuation_Q_<Q>}\\
\frac{\lambda^2}{16}\,\E\langle (Q - \E\,\langle Q\rangle_{t,R})^2 \rangle_{t,R}
&\leq\E\langle (\cL - \E\,\langle \cL \rangle_{t,R})^2 \rangle_{t,R}\;.\label{upperbound_fluctuation_Q_E<Q>}
\end{align}
\end{lemma}
\begin{IEEEproof}
Fix $(t,R) \in [0,1] \times (0,+\infty)$.
By the definition \eqref{def_L} of $\cL$, we have:
\begin{align}
\E\,\langle \cL \rangle_{t,R}
	&= \frac{1}{n}\sum_{j=1}^{n} \frac{\lambda}{4} \E \langle x_j^2 \rangle_{t,R} - \frac{\lambda}{2} \, \E\big[ \langle x_j \rangle_{t,R} X_j \big]
	- \frac{1}{2}\sqrt{\frac{\lambda}{2 R}}\, \E\big[ \langle x_j \rangle_{t,R} \widetilde{Z}_j \big] \;;\label{def_E<L>}\\
\E\,\langle Q \cL \rangle_{t,R}
	&= \frac{1}{n}\sum_{j=1}^{n}  \frac{\lambda}{4}\E \langle Q x_j^2 \rangle_{t,R} -  \frac{\lambda}{2} \E\big[ \langle Q x_j \rangle_{t,R} X_j \big] 	- \frac{1}{2}\sqrt{\frac{\lambda}{2 R}}\, \E\big[ \langle Q x_j \rangle_{t,R} \widetilde{Z}_j \big]\,.\label{def_E<Q L>}
\end{align}
Integrating by parts with respect to the Gaussian random variable $\widetilde{Z}_j$, the last expectation on the right-hand side of each of \eqref{def_E<L>} and \eqref{def_E<Q L>} reads:
\begin{align}
\E\big[ \langle x_j \rangle_{t,R} \widetilde{Z}_j \big]
	&= \sqrt{\frac{\lambda R}{2}}\E\big[ \langle x_j^2 \rangle_{t,R} \big]
	-\sqrt{\frac{\lambda R}{2}} \E\big[ \langle x_j \rangle_{t,R}^2\big] \;;\label{stein_lemma_last_term_E<L>}\\
\E\big[ \langle Q x_j \rangle_{t,R} \widetilde{Z}_j \big]
	&= \sqrt{\frac{\lambda R}{2}} \E\big[ \langle Q x_j^2 \rangle_{t,R} \big]
	-\sqrt{\frac{\lambda R}{2}} \E\big[ \langle Q x_j \rangle_{t,R} \langle x_j \rangle_{t,R} \big] \;.\label{stein_lemma_last_term_E<Q L>}
\end{align}
Plugging \eqref{stein_lemma_last_term_E<L>} in \eqref{def_E<L>} yields:
\begin{equation*}
	\E\,\langle \cL \rangle_{t,R}
= \frac{\lambda}{2n}\sum_{j=1}^{n} \frac{1}{2} \E\big[ \langle x_j \rangle_{t,R}^2\big] - \, \E\big[ \langle x_j \rangle_{t,R} X_j \big]
= -\frac{\lambda}{4n} \sum_{j=1}^{n} \frac{\E\big[ \langle x_j \rangle_{t,R} X_j \big]}{n}
= -\frac{\lambda}{4} \E\,\langle Q \rangle_{t,R} \;,
\end{equation*}
where the second equality follows from Nishimori identity: $\E[ \langle x_j \rangle_{t,R}^2] = \E[ \langle x_j \rangle_{t,R} X_j]$.
This ends the proof of \eqref{formula_E<L>}.
Plugging \eqref{stein_lemma_last_term_E<Q L>} in \eqref{def_E<Q L>}, it comes:
\begin{multline}
\E\,\langle Q \cL \rangle_{t,R}
= \frac{\lambda}{2n}\sum_{j=1}^{n_v} \frac{1}{2}\E\big[ \langle Q x_j \rangle_{t,R} \langle x_j \rangle_{t,R} \big] -  \E\big[ \langle Q x_j \rangle_{t,R} X_j \big]\\
= \frac{\lambda}{2n}\sum_{j=1}^{n_v} \frac{1}{2}\E\big[ \langle Q \rangle_{t,R} \langle x_j X_j\rangle_{t,R} \big] -  \E\big[ \langle Q x_j \rangle_{t,R} X_j \big]
= \frac{\lambda}{2}\bigg(\frac{1}{2}\E\big[ \langle Q \rangle_{t,R}^2\big] -  \E\big[ \langle Q^2 \rangle_{t,R}\big]\bigg) \;.\label{formula_E<QL>}
\end{multline}
The second equality follows once again from Nishimori identity.
Combining \eqref{formula_E<QL>} and \eqref{formula_E<L>} yields:
\begin{align*}
\E\,\langle (Q - \E\,\langle Q \rangle_{t,R}) (\cL - \E\,\langle \cL \rangle_{t,R}) \rangle_{t,R}
&= \E\,\langle Q \cL \rangle_{t,R} - \E\,\langle Q \rangle_{t,R} \E\,\langle \cL \rangle_{t,R}\\
&= \frac{\lambda}{4} \Big(\E\big[ \langle Q \rangle_{t,R}^2\big] - 2\E\big[ \langle Q^2 \rangle_{t,R}\big] + (\E\,\langle Q \rangle_{t,R})^2\Big)\\
&= -\frac{\lambda}{4} \Big(\E\,\big\langle (Q - \langle Q \rangle_{t,R})^2 \big\rangle_{t,R} + \E\,\langle (Q - \E\,\langle Q\rangle_{t,R})^2 \rangle_{t,R}\Big) \;.
\end{align*}
The upper bound \eqref{upperbound_fluctuation_Q_E<Q>} on the fluctuation of $Q$ simply follows from this last identity:
\begin{align*}
\frac{\lambda}{4} \E\,\big\langle (Q - \E\,\langle Q\rangle_{t,R})^2 \big\rangle_{t,R}
&\leq
-\E\,\langle (Q - \E\,\langle Q \rangle_{t,R}) (\cL - \E\,\langle \cL \rangle_{t,R}) \rangle_{t,R}\\
&\leq \sqrt{\E\,\langle (Q - \E\,\langle Q \rangle_{t,R})^2 \rangle_{t, R} \,\E\,\langle (\cL - \E\,\langle \cL \rangle_{t,R})^2 \rangle_{t,R}}\;.
\end{align*}
The second inequality is a simple application of Cauchy-Schwarz inequality.

The proof of the inequality \eqref{upperbound_fluctuation_Q_<Q>} is more involved.
These two identities will be useful (just replace $Q$ by its definition):
\begin{align}
\E\,\langle (Q - \langle Q \rangle_{t,R})^2 \rangle_{t,R}
&= \frac{1}{n^2}\sum_{i,j=1}^n \E\big[X_iX_j(\langle x_i x_j \rangle_{t, R} - \langle x_i \rangle_{t, R} \langle x_j \rangle_{t, R})\big]
\label{expression_E(Q-<Q>)^2}\\
\E\bigg[\!\bigg(\langle Q \rangle_{t,R} - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\,\bigg)^{\!\! 2}\,\bigg]
&= \frac{1}{n^2}\sum_{i,j=1}^n \E\big[X_iX_j \langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}\big] - 2 \E\big[X_i \langle x_i \rangle_{t, R} \langle x_j \rangle_{t, R}^2\big]\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\quad\;\;\,
+ \E\big[\langle x_i \rangle_{t, R}^2 \langle x_j \rangle_{t, R}^2\big]\nonumber\\
&= \frac{1}{n^2}\sum_{i,j=1}^n \E\big[X_iX_j \langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}\big] - \E\big[\langle x_i \rangle_{t, R}^2 \langle x_j \rangle_{t, R}^2\big]\;.\label{expression_E(Q-<x><x>/n)^2}
\end{align}
Differentiating with respect to $R$ on both side of the identity \eqref{formula_E<L>} yields:
\begin{align}
-n\E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
+\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R}
&= \frac{n\lambda}{4}(\E\,\big\langle Q \cL \rangle_{t,R}
- \E\,\langle Q \rangle_{t,R}\langle \cL \rangle_{t,R})\nonumber\\
\Leftrightarrow\qquad
-\frac{\lambda}{4}\Big(\E\,\big\langle Q \cL \rangle_{t,R}
- \E\,\langle Q \rangle_{t,R}\langle \cL \rangle_{t,R}\Big)
&= \E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
-\frac{1}{n}\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R} \;.\label{identity_E<QL>-E<Q><L>}
\end{align}
Next, we simplify the left-hand side of \eqref{identity_E<QL>-E<Q><L>}. By definition, we have:
\begin{multline}
\E\,\langle Q \rangle_{t,R}\langle \cL \rangle_{t,R}\\
= \frac{1}{n}\sum_{j=1}^{n}  \frac{\lambda}{4}\E\big[\langle Q \rangle_{t,R} \langle x_j^2 \rangle_{t,R}\big] -  \frac{\lambda}{2} \E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R} X_j \big] 	- \frac{1}{2}\sqrt{\frac{\lambda}{2 R}}\, \E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R} \widetilde{Z}_j \big]\;.\label{def_E<Q><L>}
\end{multline}
After an integration by parts with respect to $\widetilde{Z}_j$ the third expectation in the summand of \eqref{def_E<Q><L>} reads:
\begin{align*}
&\E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R} \widetilde{Z}_j \big]\\
&\qquad\qquad=
\sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q x_j \rangle_{t,R} \langle x_j \rangle_{t,R} \big]
+ \sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q \rangle_{t,R} \langle x_j^2 \rangle_{t,R} \big]
-2 \sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R}^2 \big]\\
&\qquad\qquad=
\sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q \rangle_{t,R} \langle x_j X_j \rangle_{t,R} \big]
+ \sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q \rangle_{t,R} \langle x_j^2 \rangle_{t,R} \big]
-2 \sqrt{\frac{\lambda R}{2}}\E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R}^2 \big]\;.
\end{align*}
Plugging this result back in \eqref{def_E<Q><L>} gives:
\begin{align}
\E\langle Q \rangle_{t,R}\langle \cL \rangle_{t,R}
&= \frac{\lambda}{2n}\sum_{j=1}^{n} \E\big[ \langle Q \rangle_{t,R} \langle x_j \rangle_{t,R}^2 \big]
- \frac{3}{2}\E\big[ \langle Q \rangle_{t,R} \langle x_j X_j \rangle_{t,R} \big]\nonumber\\
&= \frac{\lambda}{2}\E\bigg[ \langle Q \rangle_{t,R} \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2 \bigg]
- \frac{3\lambda}{4}\E\big[ \langle Q \rangle_{t,R}^2 \big]\;.\label{formula_E<Q><L>}
\end{align}
Finally, combining \eqref{formula_E<QL>} and \eqref{formula_E<Q><L>} yields the following expression for the left-hand side of \eqref{identity_E<QL>-E<Q><L>}:
\begin{align}
&-\frac{\lambda}{4}\Big(\E\,\big\langle Q \cL \rangle_{t,R}
- \E\,\langle Q \rangle_{t,R}\langle \cL \rangle_{t,R}\Big)\nonumber\\
&\qquad\qquad\qquad= \frac{\lambda^2}{8} \bigg(\E\big[ \langle Q^2 \rangle_{t,R}\big]
-\E\big[ \langle Q \rangle_{t,R}^2\big]
+ \E\bigg[ \langle Q \rangle_{t,R} \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2 \,\bigg]
-\E\big[ \langle Q \rangle_{t,R}^2\big]\bigg)\nonumber\\
&\qquad\qquad\qquad= \frac{\lambda^2}{8} \Bigg(\E\big[ \langle (Q-\langle Q \rangle_{t,R})^2 \rangle_{t,R}\big]
-\E\bigg[ \bigg(\langle Q \rangle_{t,R}- \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\,\bigg)^{\!\! 2}\, \bigg]\Bigg)\nonumber\\
&\qquad\qquad\qquad= \frac{\lambda^2}{8n^2} \sum_{i,j=1}^n
 \E\big[X_iX_j\langle x_i x_j \rangle_{t, R}\big]
-2\E\big[X_iX_j \langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}\big] +\E\big[\langle x_i \rangle_{t, R}^2 \langle x_j \rangle_{t, R}^2\big]\nonumber\\
&\qquad\qquad\qquad= \frac{\lambda^2}{8n^2} \sum_{i,j=1}^n
\E\big[\big(\langle x_i x_j \rangle_{t, R} - \langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}\big)^2\big]\label{formula_E<QL>-E<Q><L>}\;.
\end{align}
The second-to-last equality follows from \eqref{expression_E(Q-<Q>)^2} and \eqref{expression_E(Q-<x><x>/n)^2}, while the factorization in the last equality is easily obtained after applying Nishimori identity: $\E[X_iX_j \langle x_i x_j \rangle_{t, R}] = \E\langle x_i x_j \rangle_{t, R}^2$ and
$\E[X_iX_j \langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}] = \E[\langle x_i x_j \rangle_{t, R}\langle x_i \rangle_{t, R}\langle x_j \rangle_{t, R}]$.
We now come back to the identity \eqref{expression_E(Q-<Q>)^2} and apply Jensen's inequality to its right-hand side to get:
\begin{multline}\label{upperbound_fluctuations_Q_<Q>_proof}
\E\,\langle (Q - \langle Q \rangle_{t,R})^2 \rangle_{t,R}
\leq
\frac{\Vert \varphi \Vert_{\infty}^2}{n^2}\sum_{i,j=1}^n\E\big[\big\vert \langle x_i x_j \rangle_{t, R} - \langle x_i \rangle_{t, R} \langle x_j \rangle_{t, R}\big\vert\big]\\
\leq \Vert \varphi \Vert_{\infty}^2\sqrt{
\frac{1}{n^2}\sum_{i,j=1}^n\E\big[\big( \langle x_i x_j \rangle_{t, R} - \langle x_i \rangle_{t, R} \langle x_j \rangle_{t, R}\big)^2\big]}\;.
\end{multline}
Combining \eqref{identity_E<QL>-E<Q><L>}, \eqref{formula_E<QL>-E<Q><L>} and \eqref{upperbound_fluctuations_Q_<Q>_proof} yields the inequality \eqref{upperbound_fluctuation_Q_<Q>}.
\end{IEEEproof}
\subsection{Concentration of \texorpdfstring{$\cL$}{L} around its expectation}
To prove concentration results on $\cL$, it will be useful to work with the free entropy $\frac{1}{n} \ln \cZ_{t,R}(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)$ where $\cZ_{t,R}(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)$ is the normalization factor of the Gibbs posterior distribution \eqref{posterior_H_t_R}.
In Appendix \ref{app:concentration_free_entropy}, we prove that this free entropy concentrates around its expectation when $n \to +\infty$.
In order to shorten notations, we define:
\begin{equation*}
F_n(t,R) \triangleq \frac{1}{n} \ln \cZ_{t,R}\big(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW \big)\,;\:
f_n(t,R) \triangleq \frac{1}{n} \E\big[\ln \cZ_{t,R}\big(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW \big)\big] = \E\,F_n(t,R) \,.
\end{equation*}

\begin{proposition}[Thermal fluctuations of $\cL$ and $Q$]\label{prop:concentration_L_on_<L>}
Assume $\varphi: \R \to \R$ is continuous and bounded.
For all positive real numbers $a < b$ and $t \in [0,1]$, we have:
\begin{align*}
	\int_a^b \E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}\,dR
&\;\leq\; \frac{\lambda \Vert \varphi \Vert_{\infty}^2}{4n} \bigg(\frac{\ln(b/a)}{2} + 1 \bigg)\;;\\
\frac{\lambda}{4}\,\int_a^b \E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\,\bigg)^{\!\! 2} \,\bigg\rangle_{\!\! t,R}\,dR
&\;\leq\; \Vert \varphi \Vert_{\infty}^3\sqrt{\frac{\lambda (b-a)}{2n}}\;.
\end{align*}
\end{proposition}
\begin{IEEEproof}
Fix $(n,t) \in \mathbb{N}^* \times [0,1]$.
Note that $\forall R \in (0, +\infty)$:
\begin{equation}\label{first_derivative_fn}
\frac{\partial f_n}{\partial R}\bigg\vert_{t,R}
= -\frac{1}{n}\E\Bigg[\Bigg\langle \frac{\partial \cH_{t,R}(\bx;\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)}{\partial R} \Bigg\rangle_{\!\! t,R}\,\Bigg]
=-\E\,\langle \cL \rangle_{t,R} \;.
\end{equation}
Further differentiating, we obtain:
\begin{align}
\frac{\partial^2 f_n}{\partial R^2}\bigg\vert_{t,R}
	&= \E\bigg[\bigg\langle \cL \,\frac{\partial \cH_{t,R}}{\partial R} \bigg\rangle_{\!\! t,R}\,\bigg]
	-\E\bigg[\langle \cL \rangle_{t,R}\,
	\bigg\langle \frac{\partial \cH_{t,R}}{\partial R} \bigg\rangle_{\!\! t,R}\,\bigg]
	-\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R}\nonumber\\
	&=n\E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	-\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R}\;.\label{second_derivative_f_n_R}
\end{align}
It follows directly from \eqref{second_derivative_f_n_R} and the definition \eqref{def_L} of $\cL$ that:
\begin{equation}\label{thermal_fluctuation_L}
\E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	= \frac{1}{n}\frac{\partial^2 f_n}{\partial R^2}\bigg\vert_{t,R}
	+ \frac{1}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\E\big[\langle \bx \rangle_{t,R}^T \widetilde{\bZ}\,\big]}{n^2}
\end{equation}
We start with upper bounding the integral over the second summand on the right-hand side of \eqref{thermal_fluctuation_L}.
Thanks to an integration by parts with respect to $\widetilde{Z}_j$, $j \in \{1,\dots,n_u\}$, it comes:
\begin{equation}
\frac{1}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\E\big[\langle \bx \rangle_{t,R}^T \widetilde{\bZ}\,\big]}{n^2}
= \frac{\lambda}{8 R}\frac{\E\big[\langle \Vert \bx \Vert^2 \rangle_{t,R} - \Vert \langle \bx \rangle_{t,R} \Vert^2\,\big]}{n^2}
\leq \frac{\lambda \Vert \varphi \Vert_{\infty}^2}{8 R n}\:.
\end{equation}
Therefore:
\begin{equation}\label{upperbound_int_dL/dR}
\int_a^b \frac{dR}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\E\big[\langle \bx \rangle_{t,R}^T \widetilde{\bZ}\,\big]}{n^2}
\leq \frac{\lambda \Vert \varphi \Vert_{\infty}^2}{8 n} \ln(b/a) \:.
\end{equation}
It remains to upper bound $\int_a^b \frac{dR}{n}\frac{\partial^2 f_n}{\partial R^2}\big\vert_{t,R}
		= \frac{1}{n}\frac{\partial f_n}{\partial R}\big\vert_{t,R=b} - \frac{1}{n}\frac{\partial f_n}{\partial R}\big\vert_{t,R=a}$.
Note that $\forall R \in (0,+\infty)$:
\begin{equation}\label{upperbound_derivative_fn_R}
0 \leq \frac{\partial f_n}{\partial R}\bigg\vert_{t,R}
= - \E\,\langle \cL \rangle_{t,R}
= \frac{\lambda}{4} \E\,\langle Q \rangle_{t,R}
= \frac{\lambda}{4n} \E\,\Vert \langle \bx \rangle_{t,R} \Vert^2
\leq \frac{\lambda}{4}\Vert \varphi \Vert_{\infty}^2 \:,
\end{equation}
where the first equality follows from \eqref{first_derivative_fn}, the second one from \eqref{formula_E<L>} in Lemma~\ref{lemma:computation_E<L>_and_others}, and the third one from Nishimori identity.
Combining both \eqref{upperbound_int_dL/dR} and \eqref{upperbound_derivative_fn_R}, we finally get the first inequality:
\begin{equation*}
\int_a^b \E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}\,dR
\leq \frac{\lambda \Vert \varphi \Vert_{\infty}^2}{4n} \bigg(\frac{\ln(b/a)}{2} + 1 \bigg)\;.
\end{equation*}
To prove the second inequality, we first integrate both sides of the inequality \eqref{upperbound_fluctuation_Q_<Q>} with respect to $R$ and then use Cauchy-Schwarz inequality. We obtain:
\begin{multline}
\frac{\lambda}{4}\int_a^b \E\,\langle (Q - \langle Q \rangle_{t,R})^2 \rangle_{t,R}\,dR\\
\leq \Vert \varphi \Vert_{\infty}^2\sqrt{\frac{b-a}{2}\int_a^b \bigg(\E\,\big\langle \big(\cL - \langle \cL \rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	-\frac{1}{n}\E\,\bigg\langle \frac{\partial \cL }{\partial R} \bigg\rangle_{\!\! t,R}\,\bigg)dR}\\
= \Vert \varphi \Vert_{\infty}^2\sqrt{\frac{b-a}{2}\int_a^b \frac{dR}{n}\frac{\partial^2 f_n}{\partial R^2}\bigg\vert_{t,R}}
\leq \Vert \varphi \Vert_{\infty}^3\sqrt{\frac{\lambda (b-a)}{8n}}\;.\label{upperbound_integral_E<(Q_<Q>)^2>}
\end{multline}
Finally, note that:
\begin{align}
\E\,\bigg\langle \bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\bigg)^{\!\! 2} \bigg\rangle_{\!\! t,R}
&= \E\,\big\langle \big( Q - \langle Q \rangle_{t,R}\big)^2\big\rangle_{t,R}
+ \E \bigg[\bigg( \langle Q \rangle_{t,R} - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\bigg)^{\!\! 2} \bigg]\nonumber\\
&= \E\,\big\langle \big( Q - \langle Q \rangle_{t,R}\big)^2\big\rangle_{t,R}
+ \E \bigg[\bigg\langle Q  - \frac{\langle \bx \rangle_{t,R}\bx}{n} \bigg\rangle_{\!\! t,R}^{\!\! 2}\,\bigg]\nonumber\\
&\leq \E\,\big\langle \big( Q - \langle Q \rangle_{t,R}\big)^2\big\rangle_{t,R}
+ \E \bigg[\bigg\langle \bigg(Q  - \frac{\langle \bx \rangle_{t,R}\bx}{n}\bigg)^{\!\! 2} \bigg\rangle_{\!\! t,R}\,\bigg]\label{proof1_upperbound_fluctuation_Q_<x><x>/n}\\
&= \E\,\big\langle \big( Q - \langle Q \rangle_{t,R}\big)^2\big\rangle_{t,R}
+ \E \bigg[\bigg\langle \bigg(Q  - \frac{\langle \bx \rangle_{t,R}\bX}{n}\bigg)^{\!\! 2} \bigg\rangle_{\!\! t,R}\,\bigg]\label{proof2_upperbound_fluctuation_Q_<x><x>/n}\\
&= 2 \E\,\big\langle \big( Q - \langle Q \rangle_{t,R}\big)^2\big\rangle_{t,R} \;.\label{upperbound_fluctuation_Q_<x><x>/n}
\end{align}
The inequality \eqref{proof1_upperbound_fluctuation_Q_<x><x>/n} follows from Jensen's inequality, while the equality \eqref{proof2_upperbound_fluctuation_Q_<x><x>/n} is a simple application of Nishimori identity.
The inequalities \eqref{upperbound_integral_E<(Q_<Q>)^2>} and \eqref{upperbound_fluctuation_Q_<x><x>/n} together give the second inequality of the proposition.
\end{IEEEproof}

\begin{proposition}[Quenched fluctuations of $\cL$]\label{prop:concentration_<L>_on_E<L>}
Suppose that \ref{hyp:S_bounded_support} and \ref{hyp:varphi} hold.
Let $M >0$.
For $n$ large enough, there exists a constant $C$, which depends only on $\Vert \varphi \Vert_{\infty}$, $\Vert \varphi' \Vert_{\infty}$, $\Vert \varphi'' \Vert_{\infty}$, $M_S$, $\lambda$ and $M$, such that $\forall (a,b) \in (0,M)^2: a < \min\{1,b\}$, $\forall \delta \in (0,a)$, $\forall t \in [0,1]$:
\begin{equation}
	\int_{a}^{b} \E\,\big[\big(\langle \cL \rangle_{t,R}-\E\,\langle \cL \rangle_{t,R}\,\big)^2\,\big]\,dR
	\leq C\bigg(\frac{1}{\delta^2 n} - \frac{\ln(a)}{n} + \frac{\delta}{a-\delta} \bigg)\,.
\end{equation}
\end{proposition}
\begin{IEEEproof}
	Fix $(n,t) \in \mathbb{N}^* \times [0,1]$. For all $R \in (0,+\infty)$, we have:
	\begin{align}
		\frac{\partial F_n}{\partial R}\bigg\vert_{t,R}
		&=-\langle \cL \rangle_{t,R} \;;\\
		\frac{\partial^2 F_n}{\partial R^2}\bigg\vert_{t,R}
		&=n \big\langle \big(\cL - \langle \cL\rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	- \frac{1}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\langle \bx \rangle_{t,R}^T \widetilde{\bZ}}{n}\;;\label{quenched:2ndDeriv_Fn}\\
		\frac{\partial f_n}{\partial R}\bigg\vert_{t,R}
		&=-\E\,\langle \cL \rangle_{t,R}\;;\\
		\frac{\partial^2 f_n}{\partial R^2}\bigg\vert_{t,R}
		&=n \E\,\big\langle \big(\cL - \langle \cL\rangle_{t,R}\big)^{2}\,\big\rangle_{t,R}
	- \frac{1}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\E\big[\langle \bx \rangle_{t,R}^T \widetilde{\bZ}\,\big]}{n}\,.
	\end{align}
	The second term on the right-hand side of \eqref{quenched:2ndDeriv_Fn} can be upper bounded with Cauchy-Schwarz inequality:
	\begin{equation}\label{upperbound_2ndterm_2ndDeriv_Fn}
	\Bigg\vert\frac{1}{4 R}\sqrt{\frac{\lambda}{2R}}\frac{\langle \bx \rangle_{t,R}^T \widetilde{\bZ}}{n}\Bigg\vert
	\leq \frac{1}{4 R}\sqrt{\frac{\lambda}{2R}} \frac{\Vert \langle \bx \rangle_{t,R} \Vert\, \Vert \widetilde{\bZ} \Vert}{n}
	\leq \frac{\Vert \varphi \Vert_{\infty}}{4 R}\sqrt{\frac{\lambda}{2R}} \frac{\Vert \widetilde{\bZ} \Vert}{\sqrt{n}}\;.
	\end{equation}
	We now define for all $R \in (0, +\infty)$:
	\begin{align}
		F(R) &\triangleq F_n(t,R) - \Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda R}{2}} \frac{\Vert \widetilde{\bZ} \Vert}{\sqrt{n}}\:;\\
		f(R) &\triangleq f_n(t,R) - \Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda R}{2}}\frac{\E\,\Vert \widetilde{\bZ} \Vert}{\sqrt{n}}\,.
	\end{align}
	$F$ is convex on $(0, +\infty)$ as it is twice differentiable with a nonnegative second derivative by \eqref{quenched:2ndDeriv_Fn} and \eqref{upperbound_2ndterm_2ndDeriv_Fn}.
	The same holds for $f$.

	We will apply the following standard result to these two convex functions (we refer to \cite{barbier_adaptive_2019} for a proof):
	\begin{lemma}[An upper bound for differentiable convex functions]\label{lemma:diff_convex_functions}
		Let $g$ and $G$ be two differentiable convex functions defined on an interval $I\subseteq \mathbb{R}$.
		Let $r \in I$ and $\delta > 0$ such that $r \pm \delta \in I$. Then
		\begin{equation}
		\vert G'(r) - g'(r) \vert
		\leq C_{\delta}(r) + \frac{1}{\delta}\sum_{u \in \{-\delta,0,\delta\}} \vert G(r+u) - g(r+u) \vert \,,
		\end{equation}
		where $C_{\delta}(r) = g'(r+\delta) - g'(r-\delta) \geq 0$.
	\end{lemma}

	\noindent For all $R \in (0, +\infty)$, we have:
	\begin{align}
		F(R) - f(R)
		= F_n(t,R) - f_n(t,R)
		 - \Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda R}{2}} \frac{\Vert \widetilde{\bZ} \Vert - \E\,\Vert \widetilde{\bZ} \Vert}{\sqrt{n}}\:;\label{F_minus_f}\\
		F'(R) - f'(R)
		= -\Big(\langle \cL \rangle_{t,R} - \E\,\langle \cL\rangle_{t,R}\Big)
		 - \frac{\Vert \varphi \Vert_{\infty}}{2}\sqrt{\frac{\lambda}{2R}} \frac{\Vert \widetilde{\bZ} \Vert - \E\,\Vert \widetilde{\bZ} \Vert}{\sqrt{n}} \;. \label{F'_minus_f'}
	\end{align}
	Let $C_{\delta}(r) = f'(r+\delta) - f'(r-\delta)$, which is nonnegative by convexity of $f$.
	It follows from Lemma \ref{lemma:diff_convex_functions} and the two identities \eqref{F_minus_f} and \eqref{F'_minus_f'} that $\forall R \in (0, +\infty)$, $\forall \delta \in (0,R)$:
	\begin{align*}
		\big\vert \langle \cL \rangle_{t,R} - \E\,\langle\cL \rangle_{t,R}\big\vert
		&\leq
		\frac{\Vert \varphi \Vert_{\infty}}{2}\sqrt{\frac{\lambda}{2R}} \frac{\big\vert \Vert \widetilde{\bZ} \Vert - \E\,\Vert \widetilde{\bZ} \Vert \big\vert}{\sqrt{n}}
		+ C_{\delta}(R)\\
		&\qquad\qquad\qquad\qquad\qquad\qquad
		+ \frac{1}{\delta}\sum_{x \in \{-\delta,0,\delta\}} \vert F(R+x) - f(R+x)\vert\\
		&\leq
		\Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda}{2}} \bigg(\frac{1}{2\sqrt{R}} + 3\sqrt{R}\bigg)
		\frac{\big\vert \Vert \widetilde{\bZ} \Vert - \E\,\Vert \widetilde{\bZ} \Vert \big\vert}{\sqrt{n}}
		+ C_{\delta}(R)\\
		&\qquad\qquad\qquad\qquad\qquad\qquad
		+ \frac{1}{\delta}\sum_{x \in \{-\delta,0,\delta\}} \vert F_n(t,R + x) - f_n(t,(R + x)\vert \;.
	\end{align*}
	Thanks to the inequality $(\sum_{i=1}^{m} v_i)^2 \leq m \sum_{i=1}^{m} v_i^2$, this directly implies $\forall R \in (0, +\infty)$, $\forall \delta \in (0,R)$:
	\begin{multline}\label{upperbound_variance_thermal_L}
		\E\big[\big( \langle \cL \rangle_{t,R} - \E\,\langle\cL \rangle_{t,R}\big)^{2}\,\big]
		\leq 		5 \Vert \varphi \Vert_{\infty}^2\frac{\lambda}{2}
		\bigg(\frac{1}{4 R} + 3 + 9 R\bigg) \, \frac{\Var \Vert \widetilde{\bZ} \Vert}{n}
		+ 5C_{\delta}(R)^2\\
		+ \frac{5}{\delta^2}\sum_{x \in \{-\delta,0,\delta\}} \E\big[\big(F_n(t,R + x) - f_n(t,R + x)\big)^2\big]\,.
	\end{multline}
	The next step is to bound the integral of the three summands on the right-hand side of \eqref{upperbound_variance_thermal_L}.
	By \cite[Theorem 3.1.1]{vershynin_2018}, there exists $C_1$ such that $\Var\,\Vert\widetilde{\bZ}\Vert \leq C_1$ independently of the dimension $n$. Then:
	\begin{equation}\label{upperbound_1st_summand}
	\int_{a}^{b} dR \, 5 \Vert \varphi \Vert_{\infty}^2\frac{\lambda}{2}
	\bigg(\frac{1}{4 R} + 3 + 9 R\bigg) \, \frac{\Var \Vert \widetilde{\bZ} \Vert}{n}
	\leq
	5 \Vert \varphi \Vert_{\infty}^2\frac{\lambda}{2}
	\bigg(\frac{\ln(b/a)}{4} + 3b + \frac{9}{2} b^2 \bigg) \, \frac{C_1}{n}
	\,.
	\end{equation}
	Note that $C_{\delta}(R) = \vert C_{\delta}(R)\vert \leq \vert f'(R+\delta) \vert + \vert f'(R-\delta) \vert$.
	For all $R \in (0, +\infty)$, we have:
	\begin{equation}\label{upperbound_f'}
		\vert f'(R) \vert
		\leq
		\big\vert \E\,\langle \cL \rangle_{t,R} \big\vert
		+ \frac{\Vert \varphi \Vert_{\infty}}{2}\sqrt{\frac{\lambda}{2R}} \frac{\E\,\Vert \widetilde{\bZ} \Vert}{\sqrt{n}}
		\leq \frac{\Vert \varphi \Vert_{\infty}}{2}\sqrt{\frac{\lambda}{2}}
		\bigg( \sqrt{\frac{\lambda}{2}}\,\Vert \varphi \Vert_{\infty}  + \frac{1}{\sqrt{R}}\bigg)\;,
	\end{equation}
	The second inequality in \eqref{upperbound_f'} follows from
	the upper bounds
	$\vert \E\,\langle \cL \rangle_{t,R} \vert \leq \nicefrac{\lambda \Vert \varphi \Vert_{\infty}^2}{4}$ (see \eqref{upperbound_derivative_fn_R}) and
	$\E \Vert\widetilde{\bZ}\Vert \leq \sqrt{n}$.

	Thus, for the second summand, we obtain $\forall \delta \in (0,a)$:
	\begin{align}\label{upperbound_2nd_summand}
		&\int_a^b dR \, C_{\delta}(R)^2\nonumber\\
		&\qquad\quad\leq
		\Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda}{2}}
		\bigg( \sqrt{\frac{\lambda}{2}}\,\Vert \varphi \Vert_{\infty}  + \frac{1}{\sqrt{a - \delta}}\bigg)
		\int_a^b dR \, C_{\delta}(R)\nonumber\\
		&\qquad\quad= \Vert \varphi \Vert_{\infty}\sqrt{\frac{\lambda}{2}}
		\bigg( \sqrt{\frac{\lambda}{2}}\,\Vert \varphi \Vert_{\infty}  + \frac{1}{\sqrt{a-\delta}}\bigg)
		\big[\big(f(b+\delta) - f(b-\delta)\big) - \big(f(a + \delta) - f(a -\delta)\big)\big]\nonumber\\
		&\qquad\quad= \lambda \Vert \varphi \Vert_{\infty}^2\delta
\bigg( \sqrt{\frac{\lambda}{2}}\,\Vert \varphi \Vert_{\infty}  + \frac{1}{\sqrt{a-\delta}}\bigg)^{\! 2}\;.
	\end{align}
	The last inequality is a simple application of the mean value theorem.
	We finally turn to the third summand.
	By Proposition~\ref{prop:concentration_free_entropy} of Appendix \ref{app:concentration_free_entropy}, there exists a positive constant $C_2$ depending only on $a$, $b$, $\Vert \varphi \Vert_{\infty}$, $\Vert \varphi' \Vert_{\infty}$, $\Vert \varphi'' \Vert_{\infty}$, $M_S$ and $\lambda$ such that $\forall(t,R) \in [0,1] \times (0,b+a)$:
	\begin{equation}\label{upperbound_variance_free_entropy}
	\E\big[\big(F_n(t,R) - f_n(t,R)\big)^2 \,\big] \leq \frac{C_2}{n}\,.
	\end{equation}
	Using \eqref{upperbound_variance_free_entropy}, we see that the third summand satisfies $\forall \delta \in (0,a)$:
	\begin{equation}\label{upperbound_3rd_summand}
		\int_{a}^{b} \! dR \,
		\frac{5}{\delta^2}\sum_{x \in \{-\delta,0,\delta\}} \E\big[\big(F_n(t,R+x) - f_n(t,R+x)\big)^2 \,\big]
		\leq \frac{15C_2}{\delta^2 n} b \;.
	\end{equation}
	To end the proof it remains to integrate \eqref{upperbound_variance_thermal_L} over $R \in [a,b]$ and use the three upper bounds \eqref{upperbound_1st_summand}, \eqref{upperbound_2nd_summand} and \eqref{upperbound_3rd_summand}.
\end{IEEEproof}

\subsection{Concentration of \texorpdfstring{$Q$}{Q} around its expectation: proof of Proposition~\ref{prop:concentration_overlap}}
Using the upper bound \eqref{upperbound_fluctuation_Q_E<Q>}, it directly comes:
\begin{equation}
\frac{\lambda^2}{16}\int_{a}^{b} \E\,\big\langle \big(Q-\E\,\langle Q \rangle_{t,R}\,\big)^2\,\big\rangle_{t,R}\,dR
\leq \int_a^b \E\,\langle (\cL - \E\,\langle \cL \rangle_{t,R})^2 \rangle_{t,R} \,dR \;.
\end{equation}
We then use the concentration results for $\cL$, that is, Propositions~\ref{prop:concentration_L_on_<L>} and~\ref{prop:concentration_<L>_on_E<L>}, to upper bound
$$
\int_a^b \E\,\langle (\cL - \E\,\langle \cL \rangle_{t,R})^2 \rangle_{t,R} \,dR
= \int_a^b \E\,\langle (\cL - \langle \cL \rangle_{t,R})^2 \rangle_{t,R} \, dR + \int_a^b \E[(\langle \cL \rangle_{t,R} - \E\,\langle \cL \rangle_{t,R})^2\,]\,dR
$$
and prove Proposition~\ref{prop:concentration_overlap}.\hfill\IEEEQED


TITLE: irreducibility of a polynomial over $\mathbb{F}_2$
QUESTION [2 upvotes]: Is there any criterion (theorem or algorithm) to find out a given polynomial $f(x)$ is irreducible over the field $\mathbb{F}_2$?

REPLY [1 votes]: The best way to do it is to try to factor it with Berlekamp's Algorithm. Unfortunately there isn't much anything better than that.


TITLE: Find a sinusoidal function $f(x)$ that satisfies each set of properties.
QUESTION [0 upvotes]: Graph two complete cycles of your function.
Answers are not unique.
a. Period of 6 hours with a minimum value of -2 at t=0 hr and a maximum value of 2 at t=3 hr.
b. Period of 24 hours with a maximum value of 20 at t=6 hr and a minimum value of 10 at t=18 hr.
I'm confused because what does this have to do with hours? Aren't the units supposed to be in radians? Also, do I just follow the $f(x)=A(\sin Bx+C)+D$ form?
Any help would be appreciated. :)

REPLY [1 votes]: It is actually very easy if you understand how the periodic functions operate:
A sine function is in range $[0 \; 2\pi]$ with period $2\pi$ but in the question we see the period is mentioned 6 hours. For a sine function with period of 6, it has to finish its period $2\pi$ in 6 hours. So the function is:
$\sin(2\pi t / 6)$
If you plot this function the domain (on the y axis) of sine function is $[-1 \; 1]$ but in the question we see -2 and 2 so we have to multiply the function by 2 to increase the domain to $[-2 \; 2]$:
$2\sin(2\pi t / 6)$
We can also simplify the sine function as follows:
$2\sin(\pi t / 3)$
now it is only the mater of finding the phase. We can see that in the question it has been mentioned that at time 0 the output is -2. In a standard $\sin(x)$ the value in $x=0$ should be 0 so we can determine that the phase is $\pi/2$.
Therefore the final function would be
$2\sin(\pi t / 3 + \pi/2) $
I hope you can figure out the other question by yourself.


text:
\section{Introduction and setting}\label{sec:intro}

In modern machine learning and high dimensional statistics one often faces regression, classification, or estimation tasks, where the dimension of the feature vectors is much larger than the effective underlying dimensionality of the structure at hand. For example, hand-written MNIST digits are presented as vectors consisting of $28\times 28$ pixels, in other words, they are binary vectors with $784$ dimensions, whereas \cite{costa_2004_38676,AudibertHein2005} estimate their effective dimension to be in the orders of $10$'s. Similarly the ISOMAP face database consists of images ($256$ levels of gray) of size $64\times 64$, i.e., vectors in
$\mathbb{R}^{4096}$, whereas the correct intrinsic dimension is only $3$ (for the vertical, horizontal pause and lighting direction). Natural images, which are generally sparse in a wavelet basis \cite{Mallat_book_1999}, are another popular example of low effective dimensionality. For natural images, a very simple model of low-dimensional structure, namely vectors with a sparse number of non-zero components, has proven immensely useful for studying these types of data structures and has led to the development of the whole area of compressed sensing \cite{CandesRombergTao_2006,Donoho_CompressedSensing2006}. Similarly, matrix completion can be performed successfully when the number of sampled matrix elements is much smaller than the total number of elements, as long as one assumes the matrix is low-rank \cite{candes2009exact}.

These and other developments have amply justified the  ``bet on sparsity principle'', which, in a nutshell, says that intrinsic low-dimensionality is often a crucial ingredient for the interpretability of high dimensional statistical models  \cite{hastie_09_elements-of.statistical-learning, RishGrabarnik2014}. In this context, it is of great importance to determine computational limits of estimation and to establish fundamental information theoretical (i.e., statistical) limits as benchmarks. Broadly speaking, exact results in the direction of computational or information theoretic limits usually fall in two categories.
The first direction, traditional in statistics and computer science,  derives  {\it finite size} bounds on thresholds marking the onset of feasible signal recovery or learning
\cite{HastieTibshiraniWainwright, wainwright2019high}. Such results usually leave out exact constants or do not always give the exact asymptotics.
The second approach, is an {\it average case} approach (in the spirit of the statistical mechanics treatment of high dimensional systems), that models feature vectors by a {\it random ensemble}, taken as a set of random vectors with independently identically distributed (i.i.d.) components, and a small but fixed fraction of non-zero components. For example, the distribution might be a Bernoulli distribution, denoted ${\rm Ber}(\rho_n)$ with $0< \rho_n < 1$ and $\rho_n\to \rho > 0$ fixed, as the dimension of the vectors $n\to +\infty$.
In Bayesian settings with known priors and hyper-parameters this approach has been highly successful, yielding exact formulas for the mutual information and minimum mean-square error (MMSE), as well as exact expressions (with constants) for statistical and computational message passing phase transition thresholds in the limit of {\it infinite dimensions} \cite{Zdeborov2016}. While the mathematical analysis of this approach is well developed in compressed sensing, generalized linear estimation, or rank-one noisy matrix and tensor estimation \cite{barbier_allerton_RLE,9079920,private,barbier2017phase,2016arXiv161103888L,2017arXiv170200473M,XXT,BarbierM17a,BarbierMacris2019,2017arXiv170108010L,2017arXiv170910368B,mourrat2019hamilton}, the cited works all fall short of addressing the ``true'' sparse limit where $\rho_n \to 0$ instead of the limit being fixed (i.e., $\rho_n\to \rho > 0$) as $n\to + \infty$; {to be more precise we manage to tackle the regime $\rho_n=\Omega(n^{-\beta})$ for $\beta\in[0,1/6)$ for the information-theoretic analysis, and $\rho_n=\Omega((\ln n)^{-\alpha})$ for any positive  fixed $\alpha$ for the algorithmic results. The terminology ``true sparsity'' is employed in order to emphasize this contrast.} To the best of our knowledge the only works addressing this ``true'' sparse limit, in the average case approach for statistical phase transitions, are \cite{david2017high, reeves2019all} which consider linear regression.

In this work, we address the issue of ``true'' sparsity in the average case approach for the problem of rank-one matrix estimation from noisy observations of the entries.
Low-rank matrix estimation (or factorization) is an important problem with numerous applications in image processing, principal component analysis (PCA), machine learning, DNA microarray data, and tensor decompositions. We determine information theoretic limits of the problem as well as computational limits of an approximate message passing algorithm \cite{Kabashima_2003,bayati2011dynamics, Donoho10112009, krz12, MontChap11, Rangan11} for signal estimation in the case of a noisy symmetric rank-one matrix model. Let us now introduce the model.

{\bf Setting:} In the {\it sparse spiked Wigner matrix model} we consider a sparse signal-vector $\bX = (X_1, \ldots, X_n)\in \mathbb{R}^n$ with i.i.d.\ components distributed according to
$P_{X,n} = \rho_n p_X+(1-\rho_n)\delta_0$,

where $\delta_0$ is the Dirac mass at zero and $\rho_n \in (0,1]^\mathbb{N}$ is a sequence of weights that will eventually tend to $0$; the signal has in expectation a {\it sub-linear} number $n\rho_n$ of non-zero components. For the distribution $p_X$ we assume that $i)$ it is independent of $n$, $ii)$ it has finite support in an interval $[-S,S]$, $iii)$ it has second moment equal to $1$ (without loss of generality). One has access to the symmetric data matrix $\bW\in \mathbb{R}^{n\times n}$ with noisy entries

\begin{align}\label{WSM}
\bW = \sqrt{\frac{\lambda_n}{n}} \bX\otimes \bX +  \bZ\,, \ \ \text{or componentwise} \ \ W_{ij} = \sqrt{\frac{\lambda_n}{n}} X_iX_j +  Z_{ij}\,,  \quad 1\le i<j\le n
\end{align}

where $\lambda_n >0$ controls the strength of the signal and the noise is i.i.d.\ gaussian $Z_{ij}\sim{\cal N}(0,1)$ for $i<j$ and symmetric $Z_{ij}=Z_{ji}$. Notice that the matrix $\bW$ can be viewed as a sum of a gaussian matrix from the Wigner ensemble perturbed by a rank-one matrix, $\bX \bX^\intercal$ (the ``spike''). We focus, in particular,
on binary $\bX$ generated with i.i.d.\ Bernoulli entries $X_i \sim P_{X,n}= {\rm Ber}(\rho_n)$, or Bernoulli-Rademacher entries, $X_i\sim P_{X,n}=(1-\rho_n)\delta_0 + \rho_n\frac12(\delta_{-1}+\delta_1)$. In the Bayesian setting, we suppose that the prior $P_{X,n}$ and hyper-parameters are known.
As we will see, when $\rho_n\to 0$, non-trivial estimation is possible only when $\lambda_n\to +\infty$.

The goal is to estimate the sparse spike $\bX \otimes \bX$ from the data $\bW$. In the spiked Wigner model with linear sparsity, a class of polynomial-time algorithms, referred to as approximate message passing or AMP, have been shown to provide Bayes-optimal signal estimation for some problem settings asymptotically as $n \rightarrow +\infty$ \cite{deshpande2015finding, deshpande2014information, montanari2017estimation}. Moreover, AMP algorithms have been applied successfully for signal recovery to a number of other low-rank matrix estimation problems\cite{vila2015hyperspectral, fletcher2018iterative, parker2014bilinear, montanari2015non} and, based on bold conjectures from the statistical physics literature, it is suggested that the estimation performance of AMP is the

best among polynomial-time algorithms. Again, AMP is also provably optimal in some parameters regimes.
In this work, we study the properties of an AMP algorithm designed for signal estimation for the spiked Wigner matrix model in the sub-linear sparsity regime and compare its performance to benchmarks established by the information theoretic limits. This analysis provides a better understanding of the computational vs.\ theoretical gaps posed by the problem.

{\bf Some background and related work:} In recent years, there has been much progress in understanding such spiked matrix models, which have played a crucial role in the analysis of threshold phenomena in high-dimensional statistical models for almost two decades, but most of this work has focused on standard settings, by which we mean problem settings where the distribution
$P_X$ is fixed independent of the problem dimension $n$. This means that the expected number of non-zero components of $\bX$, even if ``small'', will scale {\it linearly} with $n$. Early rigorous results found in \cite{baik2005phase} determined the location of the information theoretic phase transition point in a spiked covariance model using spectral methods, and \cite{peche2006largest,feral2007largest} did the same for the Wigner case. More recently, the information theoretic limits and those of hypothesis testing have been derived, with the additional structure of sparse vectors, for large but finite sizes \cite{amini2009,pmlr-v75-brennan18a,gamarnik2019overlap}. A lot of efforts have also been devoted to computational aspects of sparse PCA with many remarkable results \cite{deshpande2014information,Cai2015,krauthgamer2015,JMLR:v17:15-160,wang2016,pmlr-v30-Berthet13,Ma:2015:SLB:2969239.2969419,gamarnik2019overlap,pmlr-v75-brennan18a}. The picture that has emerged is that the information theoretic and computational phase transition regimes are not on the same scale and that the computational-to-statistical gap diverges in the limit of vanishing sparsity.
However, the exact thresholds with constants as well as the behaviour of the mean-square errors remained unknown.

Using heuristic methods from the statistical physics of spin glass theory (the so-called replica method \cite{mezard2009information}), the authors of \cite{2017arXiv170100858L} observed an interesting phenomenology of the information theoretical and computational limits with sharp phase transitions as $n\to +\infty$. The rigorous mathematical theory of these phase transitions is now largely under control. On one hand, an approximate message passing algorithm for signal recovery can be rigorously analyzed via its state evolution \cite{bolthausen2014iterative,bayati2011dynamics,Donoho10112009}, and on the other hand, the asymptotic mutual information per variable between the hidden spike and data matrices has been rigorously computed in a series of works using various methods (cavity method, spatial coupling, interpolation methods, PDE techniques) \cite{korada2009exact,krzakala2016mutual,XXT,2016arXiv161103888L,2017arXiv170108010L,2017arXiv170200473M,BarbierM17a,BarbierMacris2019,2017arXiv170910368B,el2018estimation,barbier2019mutual,mourrat2019hamilton}. The information theoretic phase transitions are then signaled by singularities, as a function of the signal strength, in the limit of the mutual information per variable when $n\to +\infty$.
The phase transition also manifests itself as a jump discontinuity in the minimum mean-square error (MMSE)\footnote{This is the generic singularity and one speaks of a first order transition. In special cases the MMSE may be continuous with a higher discontinuous derivative of the mutual information.}.
Once the mutual information is known, it is usually possible to deduce the MMSE using so-called  I-MMSE relations \cite{GuoShamaiVerdu_IMMSE,guo2011estimation}. Essentially, the MMSE can be accessed by differentiating the mutual information with respect to the signal-to-noise strength. Closed form expressions for the asymptotic mutual information therefore allow
to benchmark the fundamental information theoretical limits of estimation. We also point the reader towards the works \cite{perry2018optimality,alaoui2017finite,alaoui2018detection} which derive limits of detecting the presence of a spike in a noisy matrix, rather than estimating it.

Finally, similar phase transitions in sub-linear sparsity regimes for binary signals have been studied in the context of high-dimensional linear regression or compressed sensing for support recovery \cite{david2017high,reeves2019all}. These works focus on the MMSE and prove the occurrence of the $0-1$ phase transition, which they called an ``all-or-nothing'' phenomenon. We note that our approach is technically very different in that it determines the variational expressions for mutual informations and finds the transitions as a consequence. Moreover these works do not deal with algorithmic phase transitions, while we consider here the one of AMP.

{\bf Our contributions:} We provide new results in sparse limits along two main lines:
\begin{itemize}
\item
The exact statistical threshold for the sharp all-or-nothing statistical transition at the level of the MMSE. This follows from a rigorous derivation of the mutual information in the form of a variational problem.
\item
The AMP algorithmic threshold and all-or-nothing transition at the level of the AMP mean-square error. This follows from
a ``finite sample'' analysis of the approximate message passing algorithm, allowing to rigorously track its performance in sparse regimes.
\end{itemize}
Let us explain these contributions in detail.

In this work, we identify the correct {\it scaling regimes} of vanishing sparsity and diverging signal strength in which non-trivial information theoretic and algorithmic AMP phase transitions occur. Moreover, we determine the statistical-to-algorithmic gap in the scaling regime. These scalings, thresholds, as well as formulas for the mutual information, were first heuristically and numerically derived in \cite{2017arXiv170100858L} using the non-rigorous replica method of spin-glass theory and the state evolution equations for AMP. However, it must be stressed that, not only were these calculations far from rigorous, but more importantly the limit $n\to +\infty$ is taken first for a fixed parameter $\rho_n=\rho$, and the sparse limit $\rho\to 0_+$ is taken only after. Although the thresholds found in this way agree with our derivations, this is far from evident a priori. In contrast, our results are entirely rigorous and valid in the truly sparse limit. Therefore the picture found in \cite{2017arXiv170100858L} is fully vindicated. In addition, we also establish that the MMSE and AMP phase transitions are of the all-or-nothing type, a novelty of the present work.

The information theoretic analysis is done via the adaptive interpolation method \cite{BarbierM17a,BarbierMacris2019,2017arXiv170910368B}, first introduced in the non-sparse matrix estimation problems, to provide for the sparse limit, closed form expressions of the mutual information in terms of low-dimensional variational expressions (theorem~\ref{thm:ws} in section \ref{sec:matrixWinfotheorresults}). That the adaptive interpolation method can be extended to the sparse limit is interesting and not a priori obvious.
Using the I-MMSE relation and the solution of the variational problems for Bernoulli and Bernoulli-Rademacher distributions of the sparse signal, we then find that the MMSE displays an all-or-nothing phase transition (corollary~\ref{Cor1:MMSEwigner}) and we determine the exact threshold (with constants).

A useful property of AMP is that in the large system limit $n \rightarrow + \infty$, its performance can be exactly characterized and  rigorously analyzed through its so-called {\it state evolution}. When $\rho_n\to \rho>0$, the validity of the state evolution analysis for AMP for low-rank matrix estimation follows from the standard AMP theory \cite{bayati2011dynamics,Donoho10112009} (with some additional work needed to deal with technicalities relating to the algorithm's initialization \cite{montanari2017estimation}), however, in the sub-linear sparsity regime considered here, proving the validity of the state evolution characterization requires a new and non-trivial analysis using ``finite sample'' techniques, first developed in \cite{RushVenkataramanan}. We find that the algorithmic MSE, denoted ${\rm MSE}_{\rm AMP}$ displays an all-or-nothing transition as well and we determine the scaling of the threshold (the constant being obtained numerically). Interestingly, the transition is on a very different signal-to-noise scale as compared to the MMSE (theorem \ref{AMP-theorem} found in section \ref{sec:matrixWalgo}).

Let us describe in a bit more detail the sparse regimes we study and the corresponding thresholds.
To gain some intuition, we first note that for sub-linear sparsity, phase transitions can appear only if the signal strength tends to infinity. This can be seen from the following heuristic argument:
notice that the total signal-to-noise ratio per non-zero component\footnote{In more detail, this is equal to the signal-to-noise ratio per observation $(\lambda_n/n)\rho_n^2$ times the number of observations $\Theta(n^2)$ divided by the expected number of non-zero components $\rho_n n$.}
scales as $(\lambda_n/n)\rho_n^2n^2/(\rho_n n) = \lambda_n \rho_n$, meaning that $\lambda_n \to +\infty$ is necessary in order to have enough energy to estimate the non-zero components.
Our analysis shows that non-trivial information theoretic and AMP phase transitions occur at different scales:

\begin{itemize}

\item
{\bf Statistical phase transition regime:}
While our results are more general (see appendix A and theorem 3) our main interest is in a regime of the form
\begin{align}\label{mainregime}
\lambda_n = 4\gamma \vert \ln \rho_n\vert\rho_n^{-1}, \qquad \rho_n = \Omega(n^{-\beta}),
\end{align}
for $\beta, \gamma \in \mathbb{R}_{\ge 0}$ and $\beta$ small enough. We prove that in this regime a phase transition occurs as function of $\gamma$.

\item
{\bf Algorithmic AMP phase transition regime:}
We control the performance of AMP for a number of time-iterations $t = o(\frac{\ln n}{\ln\ln n})$ and rigorously prove that the all-or-nothing transition occurs for
\begin{align}
\lambda_n = w \rho_n^{-2}, \qquad \rho_n = \Omega((\ln n)^{-\alpha}),
\end{align}
where $w, \alpha \in \mathbb{R}_{\ge 0}$ are fixed constants (note that we can take any $\alpha >1$). Controlling the AMP iterations in this regime is already highly non-trivial, however, we conjecture that the result still holds when $\rho_n = \Omega(n^{-\beta})$ for $\beta >0$ small enough, but refining the analysis in appendix K to find the stronger result is left for future work.

\end{itemize}

The relation  $\lambda_n \sim \rho_n^{-2}$ for the AMP threshold was obtained in \cite{2017arXiv170100858L} based on a stability analysis of the linearized state evolution. However, we recall that in their setting $\rho_n=\rho$, $n\to +\infty$, and not only is the sparse limit $\rho\to 0_+$ taken after the high-dimensional limit, but also the AMP iterations are not controlled. In appendix G in the supplementary material we provide a simpler alternative argument that does not require linearizing the recursion.

We focus in particular on binary signals with $P_{X,n}$ equal to ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher $(1-\rho_n)\delta_0+\rho_n\frac12(\delta_{-1}+\delta_1)$. For these distributions we prove the existence of all-or-nothing transitions for the MMSE and ${\rm MSE}_{\rm AMP}$ {for the specific sparsity regimes stated above.}
This is illustrated in figures \ref{fig:MMSEandMI} and \ref{fig:MMSEandMSEamp}, found in sections \ref{sec:matrixWinfotheorresults} and \ref{sec:matrixWalgo}, which display, for the Bernoulli prior, the explicit asymptotic values to which the finite $n$ mutual information and MMSE converge. The results are similar for the Bernoulli-Rademacher distribution. In figure \ref{fig:MMSEandMI},
we see that as $\rho_n\to 0_+$ the (suitably normalized) mutual information approaches the broken line with an angular point at $\lambda /\lambda_c(\rho_n) =1$ where
$\lambda_c(\rho_n) = 4 \vert \ln\rho_n\vert /\rho_n$. Moreover the (suitably normalized) MMSE tends to its maximum possible value $1$ for $\lambda /\lambda_c(\rho_n) <1$, develops a jump discontinuity at $\lambda /\lambda_c(\rho_n)=1$, and takes the value $0$ when $\lambda /\lambda_c(\rho_n)>1$ as $\rho_n\to 0$. In figure \ref{fig:MMSEandMSEamp}, we observe the same behavior for ${\rm MSE}_{\rm AMP}$ as a function
of $\lambda/\lambda_{\rm AMP}(\rho_n)$, but now the algorithmic threshold is $\lambda_{\rm AMP}(\rho_n) = 1/(e \rho_n^2)$, where the constant $1/e$ is approximated numerically. Note that the same asymptotic behavior is observed in the related problem of finding a small hidden community in a graph, see figure 5 in \cite{montanari2015finding}.

config: arxiv


TITLE: Is there any structure theorem for piecewise linear functions?
QUESTION [6 upvotes]: I was wondering if such statements are known like "any piecewise linear function from $\mathbb{R}^d \rightarrow \mathbb{R}$ can be written as $\sum_{i=1}^k \alpha_i (\text{ some $2$ piece linear function})$" (for some positive integer $k$ that depends on the given function and some real numbers $\alpha_i$ and maybe the $2$ piece function is different for each $i$).

Is there something in the theory of ``tropical varieties/geometry" which relates to such a thing?

REPLY [6 votes]: If you weren't assuming the piecewise linear function $f: \mathbb R^d \to \mathbb R$ is continuous, then I think this is true: we can just choose functions
$$ f_i = \begin{cases}
\text{(some linear piece of $f$)} & \text{if in domain of linear piece} \\
0 & \text{otherwise},
\end{cases}$$
and choose all coefficients $\alpha_i = 1$, so $f = \sum_i f_i$.

If you were assuming that the function $f$ is continuous, and you want to write it as a sum of continuous two-piece linear functions, then  this is false when $d\geq 2$.
Note that if $f_i$ is a two-piece linear function which is continuous, then the set of points where $f_i$ is discontinuous (i.e. the ''break locus'' of $f_i$) must be a hyperplane in $\mathbb R^d$.
Thus if we take a finite sum $\displaystyle\sum_{1\leq i\leq k} \alpha_i f_i$ over such functions, the points of discontinuity will form a hyperplane arrangement in $\mathbb R^d$ with at most $k$ hyperplanes.
(If ''cancellation'' occurs in the locus of discontinuity, it will happen along the whole hyperplane.)
However, when $d\geq 2$ there are many possible piecewise linear continuous functions $f:\mathbb R^d \to \mathbb R$ whose break locus is not a hyperplane arrangement. The simplest example is probably
$$f(x,y) = \max\{0,x,y\} : \mathbb R^2 \to \mathbb R,$$
whose break locus is the tropical line:

[image from Frank Sottile's website ]

If we only consider the case $d = 1$, then it is true that any piecewise linear continuous function may be expressed as a sum of two-piece such functions.
In light of the above counterexample it may be tempting to conjecture that the correct generalization is that a function $\mathbb R^d \to \mathbb R$ may be expressed as a sum of $(d+1)$-piece functions, but this is not true either, e.g. for the plane conic in
$\mathbb R^2$ cut out by
$$f(x,y) = \max\{ 0, 1+x, 1+y, 1+x+y, 2x, 2y\}.$$
To explain this behavior there is a perfect analogy with polynomials over complex numbers (or any algebraically closed field), via tropical geometry / algebra:

The fundamental theorem of algebra states that any polynomial $f \in \mathbb C[x]$ may be factored as a product of linear polynomials, but it is not true that any polynomial $f \in \mathbb C[x_1,\ldots,x_d]$ has  a factorization into linear polynomials when $d\geq 2$.


TITLE: Rearranging equation help (Doppler shift - special relativity)
QUESTION [0 upvotes]: I am having trouble understanding how to rearrange the equation as shown in the picture.
How do I get from:
$\left(\lambda^{\prime} / \lambda\right)^{2}(c+V)=(c-V)$
to
$V\left(1+\left(\lambda^{\prime} / \lambda\right)^{2}\right)=c\left(1-\left(\lambda^{\prime} / \lambda\right)^{2}\right)$
image

REPLY [0 votes]: Let $$a=\frac{\lambda'^2}{\lambda^2}$$ then we have
$$ac+aV=c-V$$
so
$$ac-c=-aV-V$$
Multiplying by $-1$
$$c-ac=V(a+1)$$ so we get
$$V=\frac{c(1-a)}{a+1}$$

REPLY [0 votes]: Just collect the terms with $c$ to one side and rest to the other side, like
\begin{align}
(\lambda^{\prime} / \lambda)^{2}(c+V)&=c-V\\
(\lambda^{\prime} / \lambda)^{2}c+(\lambda^{\prime} / \lambda)^{2}V&=c-V\\
(\lambda^{\prime} / \lambda)^{2}c-c&=-V-(\lambda^{\prime} / \lambda)^{2}V\\
c((\lambda^{\prime} / \lambda)^{2}-1)&=V(-1-(\lambda^{\prime} / \lambda)^{2})\\
c(1-(\lambda^{\prime} / \lambda)^{2})&=V(1+(\lambda^{\prime} / \lambda)^{2})\\
\end{align}
The book might skip few steps here and there, it is usually expected that the reader will fill in the details.