\section{Asymptotic minimum mean-square error: proof of Theorem~\ref{theorem:asymptotic_mmse}}\label{section:asymptotic_mmse}
Let $\widehat{\bX} = \widehat{\bX}(\bY,\boldsymbol{\Phi})$ be an estimator of $\bX^*$ that is a function of the observations $\bY$ and the measurement matrix $\boldsymbol{\Phi}$.
Then the mean-square error of this estimator is $\nicefrac{\E \Vert \bX^* - \widehat{\bX} \Vert^2}{k_n} \in [0, \E_{X \sim P_0} X^2]$ where the normalization factor $k_n \coloneqq n \rho_n$ is the expected sparsity of $\bX^*$.
It is well-known that the Bayes estimator $\E[\bX^* \vert \bY, \boldsymbol{\Phi}]$ achieves the minimum mean-square error (MMSE) among all estimators of the form $\widehat{\bX}(\bY,\boldsymbol{\Phi})$.
We denote the mean-square error of the Bayes estimator by
\begin{equation}
\MMSE(\bX^* \vert \bY, \boldsymbol{\Phi}) \coloneqq \frac{\E \Vert \bX^* - \E[\bX^* \vert \bY, \boldsymbol{\Phi}] \Vert^2}{k_n} \;.
\end{equation}
The MMSE is therefore a tight lower bound on the error that we achieve when estimating $\bX^*$ from the observations $\bY$ and the known measurement matrix $\boldsymbol{\Phi}$.
For this reason a result on the MMSE is easier to interprete than a result on the normalized mutual information $\nicefrac{I(\bX^*;\bY \vert \boldsymbol{\Phi}) }{m_n}$.
In this section, we prove Theorem~\ref{theorem:asymptotic_mmse}, that is, a formula for the asymptotic MMSE when $n$ diverges to infinity while $\rho_n =\Theta(n^{-\lambda})$ with $\lambda \in (0,\nicefrac{1}{9})$ and $\alpha_n = \gamma \rho_n \vert\ln\rho_n\vert$ with $\gamma>0$.
The proof of this theorem is given at the end of this section.
The proof relies on the I-MMSE relation \cite{Guo2005Mutual} that links the MMSE to the derivative of the mutual information with respect to the signal-to-noise ratio of some well-chosen observation channel.
For this reason, we first have to determine the asymptotic mutual information of a modified inference problem in which, in addition to the observations \eqref{measurements}, we have access to the side information $\widetilde{\bY}^{(\tau)} = \sqrt{\nicefrac{\alpha_n \tau}{\rho_n}}\, \bX^* + \widetilde{\bZ}$ with $\tau > 0$ and $\widetilde{\bZ}$ an additive white Gaussian noise.
Indeed, the parameter $\tau$ is akin to a signal-to-noise ratio and the derivative of the mutual information $\nicefrac{I(\bX^*;\bY, \widetilde{\bY}^{(\tau)} \vert \boldsymbol{\Phi}) }{m_n}$ with respect to $\tau$ yields half the MMSE \cite{Guo2005Mutual}:
\begin{equation*}
\frac{\partial}{\partial \tau}\bigg(\frac{I(\bX^*;\bY, \widetilde{\bY}^{(\tau)} \vert \boldsymbol{\Phi}) }{m_n}\bigg)
= \frac{\MMSE(\bX^* \vert \bY, \widetilde{\bY}^{(\tau)}, \boldsymbol{\Phi})}{2}
\xrightarrow[\tau \to 0^+]{}
\frac{\MMSE(\bX^* \vert \bY, \boldsymbol{\Phi})}{2}\;.
\end{equation*}


\subsection{Generalized linear estimation with side information}
Let $(X^*_i)_{i=1}^n \iid P_{0,n}$ be the components of the signal vector $\bX^*$.
We now have access to the observations:
\begin{align}\label{glm_with_side_information}
\begin{cases}
Y_\mu &\sim P_{\mathrm{out}}\Big( \cdot \, \Big\vert \frac{(\boldsymbol{\Phi} \bX^*)_{\mu}}{\sqrt{k_n}} \Big)\;, \quad 1\leq \mu \leq m_n\,;\\
\widetilde{Y}_i^{(\tau)} &= \sqrt{\frac{\alpha_n}{\rho_n}\tau}\, X_i^* + \widetilde{Z}_i \quad\:,\quad 1 \leq i \leq n \;;
\end{cases}
\end{align}
where $\tau \geq 0$.
Remember that the transition kernel $P_{\mathrm{out}}$ is defined in \eqref{transition-kernel} using the activation function $\varphi$ and the probability distribution $P_{A}$.
The side information induces only a small change in the \textit{(replica-symmetric) potential} whose extremization gives the asymptotic normalized mutual information. More precisely, the potential now reads:
\begin{equation}\label{def_i_RS_extended}
i_{\scriptstyle{\mathrm{RS}}}(q, r, \tau; \alpha_n, \rho_n)
\coloneqq \frac{1}{\alpha_n}I_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}(r+\tau)\bigg) +  I_{P_{\mathrm{out}}}\big(q, \E X^2\big)- \frac{r(\E X^2 -q)}{2}  \;,
\end{equation}
where $X \sim P_0$.
We then have the following generalization of Theorem~\ref{th:RS_1layer}.


\begin{theorem}[Mutual information of the GLM with side information at sublinear sparsity and sampling rate]\label{theorem:RS_1layer_extended}
	Suppose that $\Delta > 0$ and that the following hypotheses hold:
	\begin{enumerate}[label=(H\arabic*),noitemsep]
		\item There exists $S > 0$ such that the support of $P_0$ is included in $[-S,S]$.
		\item $\varphi$ is bounded, and its first and second partial derivatives with respect to its first argument exist, are bounded and continuous. They are denoted $\partial_{x} \varphi$, $\partial_{xx} \varphi$.
		\item $(\Phi_{\mu i}) \iid \cN(0,1)$.
	\end{enumerate}
	Let $\rho_n =\Theta(n^{-\lambda})$ with $\lambda \in [0,\nicefrac{1}{9})$ and $\alpha_n = \gamma \rho_n \vert\ln\rho_n\vert$ with $\gamma>0$.
	Then for all $n \in \N^*$:
	\begin{equation}\label{bound_mutual_info_rs_formula_extended}
	\bigg\vert \frac{I(\bX^*;\bY, \widetilde{\bY}^{(\tau)}\vert \boldsymbol{\Phi}) }{m_n} - \adjustlimits{\inf}_{q \in [0,\E_{P_{0}}[X^2]\,]} {\sup}_{r \geq 0}\; i_{\scriptstyle{\mathrm{RS}}}(q, r, \tau; \alpha_n, \rho_n)\bigg\vert
	\leq \frac{\sqrt{C}\,\vert \ln n \vert^{\nicefrac{1}{6}}}{n^{\frac{1}{12}-\frac{3\lambda}{4}}} \;,
	\end{equation} 
	where $C$ is a polynomial in $\big(\tau, S,\big\Vert \frac{\varphi}{\sqrt{\Delta}} \big\Vert_\infty, \big\Vert \frac{\partial_x \varphi}{\sqrt{\Delta}} \big\Vert_\infty, \big\Vert \frac{\partial_{xx} \varphi}{\sqrt{\Delta}} \big\Vert_\infty , \lambda, \gamma\big)$ with positive coefficients.
\end{theorem}
\begin{proof}
The proof is similar to the proof of Theorem~\ref{th:RS_1layer} except for a small change in the adaptive interpolation method due to the side information.
More precisely, at $t \in [0,1]$ we have access to the observations
\begin{align}\label{adaptive_interpolation_extended}
\begin{cases}
Y_{\mu}^{(t,\epsilon)}  &\sim \qquad P_{\mathrm{out}}(\,\cdot\, \vert \, S_{\mu}^{(t,\epsilon)})\qquad\quad\:,\;\:  1 \leq \mu \leq m_n \, ; \\
\widetilde{Y}_{i}^{(t,\epsilon, \tau)} &= \sqrt{\frac{\alpha_n}{\rho_n}\tau + R_1(t,\epsilon)}\, X^*_i + \widetilde{Z}_i\:,\; 1 \leq \, i \,  \leq \, n \;\;\; ;
\end{cases}
\end{align}
where $X_i^* \iid P_{0,n}$, $\widetilde{Z}_i \iid \cN(0,1)$ and
\begin{equation*}
S_{\mu}^{(t,\epsilon)}
\coloneqq \sqrt{\frac{1-t}{k_n}}\, \sum_{i=1}^n \Phi_{\mu i} X_i^*  + \sqrt{R_2(t,\epsilon)} \,V_{\mu} + \sqrt{t+2s_n-R_2(t,\epsilon)} \,W_{\mu}^*
\end{equation*}
with $\Phi_{\mu i}, V_{\mu}, W_{\mu}^* \iid \cN(0,1)$.
The proof then goes by looking to the interpolating mutual information $\nicefrac{I((\bX^*, \bW^*);(\bY^{(t,\epsilon)}, \widetilde{\bY}^{(t,\epsilon, \tau)}) \vert \boldsymbol{\Phi})}{m_n}$, and follows exactly the same lines than the proof of Theorem~\ref{th:RS_1layer}.
In particular, the interpolation functions $(R_1, R_2)$ are chosen a posteriori as the solutions to the same second-order ordinary differential equations than for Theorem~\ref{th:RS_1layer}.
\end{proof}


Let $X^* \sim P_{0,n} \perp Z \sim \cN(0,1)$. We define for all $r \geq 0$:
$$
\psi_{P_{0,n}}(r)
	\coloneqq \E \Big[\ln \int dP_{0,n}(x) e^{-\frac{r}{2}x^2 + rX^*x + \sqrt{r}xZ} \Big]\;.
$$
Note that $I_{P_{0,n}}(r) \coloneqq I(X^*;\sqrt{r}\,X^* + Z) = \frac{r\rho_n\E[X^2]}{2} - \psi_{P_{0,n}}(r)$ where $X \sim P_0$.
For $\rho_n, \alpha_n > 0$ and $\tau \geq 0$, we denote the variational problem appearing in Theorem~\ref{th:RS_1layer} by
\begin{align}
I(\rho_n, \alpha_n, \tau) &\coloneqq \adjustlimits{\inf}_{q \in [0,\E X^2]} {\sup}_{r \geq 0}\; i_{\scriptstyle{\mathrm{RS}}}(q, r, \tau ; \alpha_n, \rho_n)\nonumber\\
&= \inf_{q \in [0,\E X^2]} \, I_{P_{\mathrm{out}}}\big(q, \E X^2\big) + \frac{\tau \E X^2}{2} 
+ \sup_{r \geq 0} \bigg\{\!\frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}(r+\tau)\bigg) \!\bigg\}\nonumber\\
&=
\inf_{q \in [0,\E X^2]} \, I_{P_{\mathrm{out}}}\big(q, \E X^2\big) + \frac{\tau (\E X^2 -q)}{2}
+ \sup_{r \geq \tau} \bigg\{\!\frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg) \!\bigg\}\,,\label{def:I(rho_n,alpha_n,tau)}
\end{align}
where $X \sim P_0$.
Similarly to what is done in Appendix~\ref{appendix:specialization_discrete_prior}, we can compute the limit of $I(\rho_n, \alpha_n, \tau)$ for a discrete distribution with finite support $P_0$.
\begin{proposition}\label{prop:limit_I(rho_n,alpha_n,tau)}
	Let $P_{0,n} \coloneqq (1-\rho_n)\delta_0 + \rho_n P_0$ where $P_0$ is a discrete distribution with finite support $\mathrm{supp}(P_0) \subseteq \{-v_K, -v_{K-1}, \dots, -v_1,v_1, v_2, \dots, v_K\}$ where $0 < v_1 < \dots < v_K < v_{K+1}=+\infty$.
	Let $\alpha_n \coloneqq \gamma \rho_n \vert \ln \rho_n \vert$ for a fix $\gamma > 0$.
	For every $\tau \in [0,\nicefrac{2}{\gamma v_K^2})$, $I(\rho_n, \alpha_n, \tau)$ defined in \eqref{def:I(rho_n,alpha_n,tau)} converges when $\rho_n \to 0^+$ and (in what follows $X \sim P_0$):
	\begin{flalign}
	&\lim_{\rho_n \to 0^+} I(\rho_n, \alpha_n, \tau)&\nonumber\\
	&\qquad\;= \min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E[X^2]\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}
	+ \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_k\}}]}{2}\bigg\}\,.\hspace{-1em}&
	\end{flalign}
\end{proposition}
\begin{proof}
Fix $\tau \in [0,\nicefrac{2}{\gamma v_K^2})$.
Define $\widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2) = I_{P_{\mathrm{out}}}(q, \E X^2)  + \frac{\tau (\E X^2 -q)}{2}$.
From \eqref{def:I(rho_n,alpha_n,tau)} we have
\begin{equation}
I(\rho_n, \alpha_n, \tau) =
\inf_{q \in [0,\E X^2]} \; \widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2)
+ \sup_{r \geq \tau} \bigg\{ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg) \!\bigg\}\,.\label{def:I_tilde(rho_n,alpha_n,tau)}
\end{equation}
Note that $\widetilde{I}_{P_{\mathrm{out}}}(\cdot, \E X^2)$ is concave nonincreasing on $[0, \E X^2]$ -- exactly as $I_{P_{\mathrm{out}}}(\cdot, \E X^2)$ --, and that the variational problem \eqref{def:I_tilde(rho_n,alpha_n,tau)} has a form similar to the quantity $I(\rho_n, \alpha_n)$ whose limit is given by Proposition~\ref{prop:limit_I(rho_n,alpha_n)_general} in Appendix~\ref{appendix:specialization_discrete_prior}.
The only difference that we have to take into account in the analysis is that the supremum is over $r \in [\tau, +\infty)$ instead of $r \in [0,+\infty)$.

Remember the definition \eqref{definition_a_rhon_k_and_b_rhon_k} of $a_{\rho_n}^{(K)}$.
By Lemma~\ref{lemma:location_r*(q)_general}, for every $q \in (\rho_n \E[X]^2, \E[X^2])$ there exists a unique $r_{n}^*(q) \in (0,+\infty)$ such that
\begin{equation}
\frac{r_{n}^*(q)q}{2} - \frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r_{n}^*(q)\bigg)
= \sup_{r \geq 0} \: \frac{rq}{2} - \frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg)\;,
\end{equation}
and $\forall q \in [a_{\rho_n}^{(K)}, \E X^2): r_{n}^*(q) \geq \nicefrac{2(1-\vert \ln \rho_n \vert^{-\frac14})}{\gamma v_K^2}$.
By assumption $\tau < \nicefrac{2}{\gamma v_K^2}$ so, for $\rho_n$ small enough, $\forall q \in [a_{\rho_n}^{(K)}, \E X^2): r_{n}^*(q) > \tau$.
It follows that $\forall q \in [a_{\rho_n}^{(K)}, \E X^2): r_n^*(q)$ satisfies
\begin{equation}\label{sup_r>tau_r_n^*}
\frac{r_{n}^*(q)q}{2} - \frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r_{n}^*(q)\bigg)
= \sup_{r \geq \tau} \: \frac{rq}{2} - \frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg)\;.
\end{equation}
Thanks to the identity \eqref{sup_r>tau_r_n^*} the same analysis leading to Propositions~\ref{proposition:limits_inf_a_b} and \ref{prop:limit_I(rho_n,alpha_n)_general} can be repeated, replacing $I_{P_{\mathrm{out}}}(\cdot, \E X^2)$ by $\widetilde{I}_{P_{\mathrm{out}}}(\cdot, \E X^2)$
(this makes no difference as we only need for $\widetilde{I}_{P_{\mathrm{out}}}(\cdot,\E X^2)$ to be concave nonincreasing),

in order to obtain the limit:
\begin{multline}\label{limit_inf_[ak,EX^2]_tau}
\lim_{\rho_n \to 0^+}
\adjustlimits{\inf}_{q \in [a_{\rho_n}^{(K)}, \E X^2]} {\sup}_{r \geq \tau}\;
\widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2)
+ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg)\\
= \min_{1 \leq k \leq K+1}\bigg\{\widetilde{I}_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
\end{multline}
Note that the limit \eqref{limit_inf_[ak,EX^2]_tau} is for the infimum over $q \in [a_{\rho_n}^{(K)}, \E X^2]$, not the infimum over ${q \in [0,\E X^2]}$. This is because, for $q \in (\rho_n \E X^2,a_{\rho_n}^{(K)})$, $r_n^*(q)$ does not necessarily satisfy \eqref{sup_r>tau_r_n^*}.
However, the limit \eqref{limit_inf_[ak,EX^2]_tau} directly implies the following upper bound on the limit superior:
\begin{equation}\label{limsup_I(rho_n,alpha_n,tau)}
\limsup_{\rho_n \to 0^+} I(\rho_n, \alpha_n, \tau)
\leq \min_{1 \leq k \leq K+1}\bigg\{\widetilde{I}_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
\end{equation}
In order to lower bound the limit inferior, we have to lower bound the infimum over $q \in [0,a_{\rho_n}^{(K)}]$ of
$\widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2)
+ \sup_{r \geq \tau} \big\{ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\big(\nicefrac{\alpha_n r}{\rho_n}\big) \big\}$.
Because $\widetilde{I}_{P_{\mathrm{out}}}(\cdot, \E X^2)$ is nonincreasing and $q \mapsto \sup_{r \geq \tau} \big\{ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\big(\nicefrac{\alpha_n r}{\rho_n}\big) \big\}$ is nondecreasing (it is the supremum of nondecreasing functions), we have:
\begin{align}
&\inf_{q \in [0,a_{\rho_n}^{(K)}]}\;
\widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2)
+ \sup_{r \geq \tau} \bigg\{ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg) \bigg\}\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\geq \widetilde{I}_{P_{\mathrm{out}}}(a_{\rho_n}^{(K)}, \E X^2)
+ \sup_{r \geq \tau} \biggl\{-\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg) \bigg\}\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\geq \widetilde{I}_{P_{\mathrm{out}}}(a_{\rho_n}^{(K)}, \E X^2)
-\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}\tau\bigg) \;.\label{lowerbound_inf_0_aK_tau}
\end{align}
The last inequality follows from $\psi_{P_{0,n}}$ being nondecreasing (see Lemma~\ref{lemma:property_I_P0n}).
We can use the computations in the proof of Lemma~\ref{lemma:limits_psi_P0n_r*} to write $\frac{1}{\alpha_n}\psi_{P_{0,n}}\big(\frac{\alpha_n \tau}{\rho_n}\big)$ more explicitly:
\begin{flalign}
&\frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n \tau}{\rho_n}\bigg)
= \frac{B_{\rho_n}}{\gamma} + \frac{\tau \E X^2}{2}  -\frac{1}{\gamma}
+ \frac{1}{\gamma}\sum_{j=1}^K p_j^{\scriptscriptstyle +} \E \bigg[\frac{\ln \widetilde{h}\big(Z,\gamma \tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\scriptscriptstyle +},\bp^{\scriptscriptstyle -}\big)}{\vert \ln \rho_n \vert}\bigg]\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad
+ \frac{1}{\gamma}\sum_{j=1}^K p_j^{\scriptscriptstyle -} \E \bigg[\frac{\ln \widetilde{h}\big(Z,\gamma \tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\scriptscriptstyle -},\bp^{\scriptscriptstyle +}\big)}{\vert \ln \rho_n \vert}\bigg]\:,\label{formula_psi_P0n_tau}
\intertext{where}
&B_{\rho_n}
= \frac{1-\rho_n}{\rho_n \vert \ln \rho_n \vert} \E \ln\bigg(1 - \rho_n + \rho_n \sum_{i=1}^K e^{-\frac{\gamma \tau}{2 v_k^2}\vert \ln \rho_n \vert} \bigg(p_i^{\scriptscriptstyle +} e^{\sqrt{\gamma \tau \vert \ln \rho_n \vert v_i^2} Z }
+ p_i^{\scriptscriptstyle -} e^{ -\sqrt{\gamma \tau \vert \ln \rho_n \vert v_i^2} Z}\bigg)\bigg)\nonumber
\intertext{and $\forall z \in \R:$}
&\widetilde{h}\big(z,\gamma \tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\pm},\bp^{\mp}\big)
= (1 - \rho_n)e^{\vert \ln \rho_n \vert \Big(1-\frac{\gamma \tau v_j^2}{2} -\sqrt{\frac{\gamma \tau v_j^2}{\vert \ln \rho_n \vert}} z\Big)}\nonumber\\
&\qquad\,
+\sum_{i=1}^K e^{-\vert \ln \rho_n \vert  \big(\frac{\gamma \tau(v_i-v_j)^2}{2} - \sqrt{\frac{\gamma \tau}{\vert \ln \rho_n \vert }} (v_i-v_j) z\big)}\Big(p_i^{\pm}
+ p_i^{\mp} e^{-2\vert \ln \rho_n \vert v_i\big(\gamma \tau v_j + z\sqrt{\frac{\gamma\tau}{\vert \ln \rho_n \vert}}\big)}\bigg)\,.\label{h_tilde_simplified_tau}
\end{flalign}
We can show, exactly as it is done for $A_{\rho_n}$ in the proof of Lemma~\ref{lemma:limits_psi_P0n_r*}, that $\vert B_{\rho_n} \vert \leq \nicefrac{1}{\vert \ln \rho_n \vert}$.
As $\tau < \nicefrac{2}{\gamma v_K^2}$ we have $\forall j \in \{1,\dots,K\}: 1-\nicefrac{\gamma \tau v_j^2}{2} > 0$,
and from \eqref{h_tilde_simplified_tau} we then easily deduce that $\forall j \in \{1,\dots,K\},\forall z \in \R:$
\begin{equation}\label{limit_h_tilde_tau}
\lim_{\rho_n \to 0^+} \frac{\ln \widetilde{h}\big(z,\gamma\tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\pm},\bp^{\mp}\big)}{\vert \ln \rho_n \vert}
= 1 - \frac{\gamma \tau v_j^2}{2}\;.
\end{equation}
By the dominated convergence theorem, making use of the pointwise limits \eqref{limit_h_tilde_tau}, we have:
\begin{multline}\label{limit_sum_E_h_tilde_tau}
\sum_{j=1}^K p_j^{\scriptscriptstyle +} \E \bigg[\frac{\ln \widetilde{h}\big(Z,\gamma\tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\scriptscriptstyle +},\bp^{\scriptscriptstyle -}\big)}{\vert \ln \rho_n \vert}\bigg]
+ p_j^{\scriptscriptstyle -} \E \bigg[\frac{\ln \widetilde{h}\big(Z,\gamma\tau \vert \ln \rho_n \vert,v_j;\rho_n, \bv, \bp^{\scriptscriptstyle -},\bp^{\scriptscriptstyle +}\big)}{\vert \ln \rho_n \vert}\bigg]\\
\xrightarrow[\rho_n \to 0^+]{} \sum_{j=1}^K (p_j^{\scriptscriptstyle +} 
+ p_j^{\scriptscriptstyle -} ) \bigg(1 - \frac{\gamma \tau v_j^2}{2}\bigg)
=1 - \frac{\gamma \tau \E X^2}{2}\;.
\end{multline}
Combining the identity \eqref{formula_psi_P0n_tau}, $\lim_{\rho_n \to 0^+} B_{\rho_n} = 0$ and the limit \eqref{limit_sum_E_h_tilde_tau} yields:
\begin{equation}\label{limit_psi_P0n_tau}
\lim_{\rho_n \to 0} \frac{1}{\alpha_n} \psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n} \tau \bigg)
= \frac{\tau \E X^2}{2}  -\frac{1}{\gamma} + \frac{1}{\gamma}\bigg(1 - \frac{\gamma \tau \E X^2}{2}\bigg) = 0\;.
\end{equation}
The lower bound \eqref{lowerbound_inf_0_aK_tau} together with the limits \eqref{limit_psi_P0n_tau} and $\lim_{\rho_n \to 0^+} a_{\rho_n}^{(K)} = 0$ (see Lemma~\ref{lemma:location_r*(q)_general}) implies:
\begin{equation}
\liminf_{\rho_n \to 0^+} \inf_{q \in [0,a_{\rho_n}^{(K)}]}\;
\widetilde{I}_{P_{\mathrm{out}}}(q, \E X^2)
+ \sup_{r \geq \tau} \bigg\{ \frac{rq}{2} -\frac{1}{\alpha_n}\psi_{P_{0,n}}\bigg(\frac{\alpha_n}{\rho_n}r\bigg) \bigg\}
\geq \widetilde{I}_{P_{\mathrm{out}}}(0, \E X^2)\;.
\end{equation}
Finally, we combine the latter inequality with the limit \eqref{limit_inf_[ak,EX^2]_tau} to obtain
\begin{equation}\label{liminf_I(rho_n,alpha_n,tau)}
\liminf_{\rho_n \to 0^+} I(\rho_n, \alpha_n, \tau)
\geq \min_{1 \leq k \leq K+1}\bigg\{\widetilde{I}_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
\end{equation}
The upper bound \eqref{limsup_I(rho_n,alpha_n,tau)} on the limit superior matches the lower bound \eqref{liminf_I(rho_n,alpha_n,tau)} on the limit inferior. Hence,
\begin{flalign*}
&\lim_{\rho_n \to 0^+} I(\rho_n, \alpha_n, \tau)
= \min_{1 \leq k \leq K+1}\bigg\{\widetilde{I}_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}&\\
&\qquad\qquad
= \min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) + \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_k\}}]}{2} +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\,;
\end{flalign*}
where the last equality follows simply from the definition of $\widetilde{I}_{P_{\mathrm{out}}}$.
\end{proof}


The next theorem is a direct corollary of Theorem~\ref{theorem:RS_1layer_extended} and Proposition~\ref{prop:limit_I(rho_n,alpha_n,tau)}.
\begin{theorem}\label{theorem:limit_mutual_info_side_info}
	Suppose that $\Delta > 0$ and that $P_{0,n} \coloneqq (1-\rho_n)\delta_0 + \rho_n P_0$ where $P_0$ is a discrete distribution with finite support $\mathrm{supp}(P_0) \subseteq \{-v_K, -v_{K-1}, \dots, -v_2, -v_1,v_1, v_2, \dots, v_{K-1}, v_K\}$ where $0 < v_1 < v_2 < \dots < v_K < v_{K+1}=+\infty$.
	Further assume that the following hypotheses hold:
	\begin{enumerate}[label=(H\arabic*),noitemsep]
		\setcounter{enumi}{1}
		\item $\varphi$ is bounded, and its first and second partial derivatives with respect to its first argument exist, are bounded and continuous. They are denoted $\partial_{x} \varphi$, $\partial_{xx} \varphi$.
		\item $(\Phi_{\mu i}) \iid \cN(0,1)$.
	\end{enumerate}
	Let $\rho_n =\Theta(n^{-\lambda})$ with $\lambda \in (0,\nicefrac{1}{9})$ and $\alpha_n = \gamma \rho_n \vert\ln\rho_n\vert$ with $\gamma>0$.
	Then $\forall \tau \in [0,\nicefrac{2}{\gamma v_K^2})$:
	\begin{flalign*}
	&\lim_{n \to +\infty} \frac{I(\bX^*;\bY,\widetilde{\bY}^{(\tau)} \vert \boldsymbol{\Phi}) }{m_n}&\\
	&\qquad\qquad\;\;= \min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) + \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_k\}}]}{2} +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
	\end{flalign*}
\end{theorem}
\subsection{Proof of Theorem~\ref{theorem:asymptotic_mmse}}
For all $n \in \mathbb{N}^*$ and $\tau \in [0,+\infty)$ we define $i_n(\tau) \coloneqq \nicefrac{I(\bX^*;\bY,\widetilde{\bY}^{(\tau)} \vert \boldsymbol{\Phi}) }{m_n}$ the normalized conditional mutual information between $\bX^*$ and the observations $\bY,\widetilde{\bY}^{(\tau)}$ -- defined in \eqref{glm_with_side_information} -- given $\boldsymbol{\Phi}$.
We place ourselves in the regime of Theorem~\ref{theorem:asymptotic_mmse}, that is, $\rho_n =\Theta(n^{-\lambda})$ with $\lambda \in [0,\nicefrac{1}{9})$ and $\alpha_n = \gamma \rho_n \vert\ln\rho_n\vert$ with $\gamma>0$.
By Theorem~\ref{theorem:limit_mutual_info_side_info} if the side-information is low enough, namely $\tau < \nicefrac{2}{\gamma v_K^2}$, then $\lim_{n \to +\infty} i_n(\tau) = i(\tau)$ where
\begin{equation}\label{def:i(tau)}
 i(\tau) \coloneqq \min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E X^2\big) + \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_k\}}]}{2} +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
\end{equation}
We first establish a few properties of the function $i_n$.
The posterior density of $\bX^*$ given the observations $(\bY,\widetilde{\bY}^{(\tau)})$ defined in \eqref{glm_with_side_information} reads:
\begin{equation}\label{posterior_density_X*_side_info}
	dP\big(\bx \big\vert \bY,\widetilde{\bY}^{(\tau)}\big) = \frac{1}{\cZ(\bY,\widetilde{\bY}^{(\tau)})} \prod_{i=1}^{n} dP_{0,n}(x_i) e^{-\frac12 \big(\widetilde{Y}_i^{(\tau)} - \sqrt{\frac{\alpha_n \tau}{\rho_n}} x_i\big)^2} \prod_{\mu=1}^{m_n} P_{\mathrm{out}}\bigg(Y_\mu \bigg\vert \frac{(\boldsymbol{\Phi} \bx)_\mu}{\sqrt{k_n}}\bigg)\;,
\end{equation}
where $\cZ(\bY,\widetilde{\bY}^{(\tau)})$ is a normalization factor.
In what follows $\bx$ denotes a $n$-dimensional random vector distributed with respect to the posterior distribution \eqref{posterior_density_X*_side_info}.
We will use the brackets $\langle - \rangle_{n,\tau}$ to denote an expectation with respect to $\bx$.
By definition of the mutual information we have:
\begin{align}
i_n(\tau)
&= -\frac{1}{m_n} \E \ln \cZ(\bY,\widetilde{\bY}^{(\tau)})
+ \frac{1}{m_n}\E\bigg[ \ln \prod_{i=1}^{n} e^{-\frac12 \big(\widetilde{Y}_i^{(\tau)} - \sqrt{\frac{\alpha_n \tau}{\rho_n}} X_i^*\big)^2} \prod_{\mu=1}^{m_n} P_{\mathrm{out}}\bigg(Y_\mu \bigg\vert \frac{(\boldsymbol{\Phi} \bX^*)_\mu}{\sqrt{k_n}}\bigg)\bigg]\nonumber\\
&= -\frac{1}{m_n} \E \ln \cZ(\bY,\widetilde{\bY}^{(\tau)})
-\frac{1}{2\alpha_n} + \E\bigg[ \ln P_{\mathrm{out}}\bigg(Y_1 \bigg\vert \frac{(\boldsymbol{\Phi} \bX^*)_1}{\sqrt{k_n}}\bigg)\bigg]\;.
\end{align}
Derivation under the expectation sign, justified by the dominated convergence theorem, yields the first derivative:
\begin{align}
i'_n(\tau)
&= \frac{1}{m_n}\sum_{i=1}^{n}\E\bigg[\bigg\langle \bigg(\widetilde{Y}_i^{(\tau)} - \sqrt{\frac{\alpha_n \tau}{\rho_n \tau}}x_i\bigg)\frac12 \sqrt{\frac{\alpha_n}{\rho_n \tau}}(X_i^* - x_i) \bigg\rangle_{\!\! n,\tau}\bigg]\nonumber\\
&= \frac{1}{m_n}\sum_{i=1}^{n}\E\bigg[\bigg\langle\bigg(\widetilde{Y}_i^{(\tau)} - \sqrt{\frac{\alpha_n \tau}{\rho_n \tau}}X_i^*\bigg)\frac12 \sqrt{\frac{\alpha_n}{\rho_n \tau}}(x_i - X_i^*)\bigg\rangle_{\!\! n,\tau}\bigg]\nonumber\\
&= \frac{1}{2m_n} \sqrt{\frac{\alpha_n}{\rho_n \tau}}\E\big[\widetilde{Z}_i (\langle x_i\rangle_{n,\tau} - X_i^*)\big]\nonumber\\
&= \frac{1}{2m_n} \sqrt{\frac{\alpha_n}{\rho_n \tau}}\sum_{i=1}^{n}\E\big[\widetilde{Z}_i \langle x_i\rangle_{n,\tau}\big]\nonumber\\
&= \frac{1}{2m_n} \frac{\alpha_n}{\rho_n}\sum_{i=1}^{n}\E\big[\langle x_i^2\rangle_{n,\tau} - \langle x_i\rangle_{n,\tau}^2\big]\nonumber\\
&= \frac{\E \Vert \bX^* - \E[\bX^* \vert \bY, \bY^{(\tau)},\boldsymbol{\Phi}] \Vert^2}{2k_n}\;.\label{i_n'(tau)_IMMSErelation}
\end{align}
The second equality above follows from Nishimori identity. The fifth equality is obtained thanks to a Gaussian integration by parts with respect to $\widetilde{Z}_i$.
The final identity \eqref{i_n'(tau)_IMMSErelation} is the I-MMSE relation previously mentioned.
Further differentiating with respect to $\tau$ and integrating by parts with respect to the Gaussian random variables $\widetilde{Z}_i$ give
\begin{equation}\label{i_n''(tau)}
i_n^{\prime\prime}(\tau)
= -\frac{1}{2 k_n}\sum_{i=1}^n \E\big[\big\langle (x_i - \langle x_i \rangle_{n,\tau})^2 \big\rangle_{n,\tau}^2\big]\;.
\end{equation}
The identity \eqref{i_n''(tau)} shows that $i_n$ is concave as its second derivative is nonpositive.
By Griffiths’ lemma it follows that whenever the pointwise limit \eqref{def:i(tau)} is differentiable at $\tau \in (0,\nicefrac{2}{\gamma v_K^2})$ we have:
\begin{equation*}
\lim_{n \to + \infty} i'_n(\tau) = i'(\tau) \;.
\end{equation*}
The final step is to determine $i'(\tau)$. Suppose that the minimization problem
\begin{equation}\label{eq:proof_minimization_problem} 
\min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E[X^2]\big) +\frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}
\end{equation}
has a unique solution $k^* \in \{1,\dots,K+1\}$. Then, there exists $\epsilon \in [0,\nicefrac{2}{\gamma v_K^2})$ such that $\forall \tau \in [0,\epsilon): k^*$ is the unique solution to the minimization problem
\begin{equation*}
\min_{1 \leq k \leq K+1}\bigg\{I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E[X^2]\big)
+ \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_k\}}]}{2} 
+ \frac{\mathbb{P}(\vert X \vert \geq v_k)}{\gamma}\bigg\}\;.
\end{equation*}
Therefore, $\forall \tau \in [0,\epsilon):$
\begin{align*}
i(\tau) &= I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_{k^*}\}}],\E[X^2]\big)
+ \frac{\tau \E[X^2 \bm{1}_{\{\vert X \vert < v_{k^*}\}}]}{2} 
+ \frac{\mathbb{P}(\vert X \vert \geq v_{k^*})}{\gamma}\;,\\
i'(\tau) &= \frac{\E[X^2 \bm{1}_{\{\vert X \vert < v_{k^*}\}}]}{2}\;.
\end{align*}
We conclude that whenever the minimization problem \eqref{eq:proof_minimization_problem} has a unique solution $k^*$ we have
\begin{equation*}
\lim_{n \to + \infty} \frac{\E \Vert \bX^* - \E[\bX^* \vert \bY, \boldsymbol{\Phi}] \Vert^2}{k_n} 
= \lim_{n \to + \infty} 2 i'_n(0) = 2i'(0) = \E[X^2 \bm{1}_{\{\vert X \vert < v_{k^*}\}}]\;.
\end{equation*}


\subsection{All-or-nothing phenomenon and its generalization}
We now look at the asymptotic MMSE as a function of the number of measurements, i.e., as a function of the parameter $\gamma$ that controls the number of measurements $m_n = \gamma \cdot n\rho_n \vert \log \rho_n \vert$.
Let $X \sim P_0$ and assume that $\mathrm{supp} \vert X \vert = K$. We place ourselves under the assumptions of Theorem~\ref{theorem:asymptotic_mmse}.
The functions $k \mapsto I_{P_{\mathrm{out}}}\big(\E[X^2 \bm{1}_{\{\vert X \vert \geq v_k\}}],\E[X^2]\big)$ and $k \mapsto \mathbb{P}(\vert X \vert \geq v_k)$ are nondecreasing and increasing on $\{1, 2, \dots, K+1\}$, respectively.
Hence, the minimization problem on the right-hand side of \eqref{limit_minimization_problem} has a unique solution denoted $k^*(\gamma)$ for all but $K$ or less values of $\gamma \in (0,+\infty)$, and ${\gamma_1 < \gamma_2 \Rightarrow k^*(\gamma_1) \geq k^*(\gamma_2)}$ (assuming $k^*(\gamma_1), k^*(\gamma_2)$ are well-defined).
By Theorem~\ref{theorem:asymptotic_mmse}, it implies that the asymptotic MMSE as a function of $\gamma$ is nonincreasing and piecewise constant; its image is included in $\{\E X^2, \E[X^2 \bm{1}_{\{\vert X \vert \leq v_{K-1}\}}],  \dots, \E[X^2 \bm{1}_{\{\vert X \vert \leq v_{1}\}}], 0\}$.
The asymptotic MMSE has at most $K$ discontinuities. As $\gamma$ increases past a discontinuity, the asymptotic MMSE jumps from $\E[X^2 \bm{1}_{\{\vert X \vert < v_{k_1^*}\}}]$ for some $k_1^* \in \{2,\dots,K+1\}$ down to a lower value $\E[X^2 \bm{1}_{\{\vert X \vert < v_{k_2^*}\}}]$ where $k_2^* \in \{1,\dots,k_1^*-1\}$.


Therefore, when $K=1$, the asymptotic MMSE has one discontinuity at $\gamma_c \coloneqq 1/I_{P_\mathrm{out}}(0,\E X^2)$ where it jumps down from $\E X^2$ to $0$: this is the all-or-nothing phenomenon previously observed in \cite{Gamarnik2017High, Reeves2019All, Reeves2019Alla} for a linear activation function $\varphi(x) = x$ and a deterministic distribution $P_0$.
Theorem~\ref{theorem:asymptotic_mmse} generalizes this all-or-nothing phenomenon to activation functions satisfying mild conditions and any discrete distribution $P_0$ whose support is included in $\{-v,v\}$ for some $v > 0$.

When $K > 1$, the phenomenology is more complex.
The asymptotic MMSE exhibits intermerdiate plateaus in between the plateaus ``$\mathrm{MMSE} = \E X^2$'' (no reconstruction at all) for low values of $\gamma$ and ``$\mathrm{MMSE} = 0$'' (perfect reconstruction) for large values of $\gamma$.
For illustration purposes we now define the following three discrete distributions with support size $K \geq 1$:
\begin{itemize}
	\item $P_{\mathrm{unif}}^{(K)}$ is the uniform distribution on $\{\sqrt{a}, 2\sqrt{a}, \dots, K \sqrt{a}\}$ with $a := \nicefrac{6}{(K+1)(2K+1)}$ so that $\E X^2 = 1$ for $X \sim P_0$.
	\item $P_{\mathrm{linear}}^{(K)}$ is the distribution on $\{\sqrt{b}, 2\sqrt{b}, \dots, K \sqrt{b}\}$ with $b := \sum_{j=1}^K \nicefrac{1}{Kj^2}$ and $P_{\mathrm{linear}}^{(K)}(i\sqrt{b}) = \nicefrac{1}{Ki^2b}$ so that $\E X^2 = 1$ and $\E[X^2 \bm{1}_{\{\vert X \vert < k\sqrt{b}\}}] = \nicefrac{k-1}{K}$ for $X \sim P_0$, i.e., the quantity $\E[X^2 \bm{1}_{\{\vert X \vert < v_k \}}]$ increases linearly with $k$.
	\item $P_{\mathrm{binom}}^{(K,p)}$ is the binomial distribution on $\{\sqrt{c}, 2\sqrt{c}, \dots, K \sqrt{c}\}$ with
	\begin{equation*}
		c = \nicefrac{1}{(K-1)(K-2)p^2 + 3(K-1)p + 1}
	\end{equation*}
	and
	$P_{\mathrm{binom}}^{(K,p)}(i\sqrt{c}) = \binom{K-1}{i-1} p^{i-1}(1-p)^{K-i}$ so that $\E X^2 = 1$.
\end{itemize}
In Figure~\ref{figure:asymptotic_mmse_delta_gamma_K=5} we plot the asymptotic MMSE (using Theorem~\ref{theorem:asymptotic_mmse}) as a function of the noise variance $\Delta$ and the parameter $\gamma$ for three different activation functions and $P_0 \in \{P_{\mathrm{unif}}^{(5)},P_{\mathrm{linear}}^{(5)}, P_{\mathrm{binom}}^{(5,0.2)} \}$.
\begin{figure}[hbt]
	\centering
	{\includegraphics[width=\linewidth]{figures/mmse_linear_relu_sign_P0uniform_K=5.png}
		\includegraphics[width=\linewidth]{figures/mmse_linear_relu_sign_P0linear_truncated_2ndmoment_K=5.png}}
	\includegraphics[width=\linewidth]{figures/mmse_linear_relu_sign_P0binomial_EX=1_K=5.png}
	\caption{\label{figure:asymptotic_mmse_delta_gamma_K=5}
		\small{Minimum mean-square error in the asymptotic regime of Theorem~\ref{theorem:asymptotic_mmse} for $\Delta \in [0,4]$ and $\gamma \in (0,10.5]$.
			\textit{From left to right:} the activation function is linear $\varphi(x) = x$, the ReLU $\varphi(x)=\max(0,x)$ and the sign function $\varphi(x) = \mathrm{sign}(x)$.
			\textit{Top to bottom:} the prior distribution $P_0$ of the nonzero elements of $\bX^*$ is $P_{\mathrm{unif}}^{(5)}$, $P_{\mathrm{linear}}^{(5)}$ and $P_{\mathrm{binom}}^{(5,0.2)}$.}}
\end{figure}
{"config": "arxiv", "file": "2006.11313/appendices/asymptotic_mmse.tex"}