Asymptotic mutual information for the binary stochastic block model

The stochastic block model is the simplest statistical model for networks with a community (or cluster) structure. As such, it has attracted considerable amount of work across statistics, machine learning, and theoretical computer science [1]–[2][3][4][5]. A random graph $\boldsymbol{G}=(V,\ E)$ from this model has its vertex set $V$ partitioned into $r$ groups, which are assigned $r$ distinct labels. The probability of edge $(i,j)$ being present depends on the group labels of vertices $i$ and $j$.

In the context of social network analysis, groups correspond to social communities [1]. For other data-mining applications, they represent latent attributes of the nodes [6]. In all of these cases, we are interested in inferring the vertex labels from a single realization of the graph.

In this paper we develop an information-theoretic viewpoint on the stochastic block model. Namely, we develop an explicit (‘single-letter’) expression for the per-vertex conditional entropy of the vertex labels given the graph. Equivalently, we compute the asymptotic per-vertex mutual information between the graph and the vertex labels. Our results hold for in the large network limit, under suitable assumptions on the model parameters. In particular, we require that the mean vertex degree in the graph diverge (albeit arbitrarily slowly). While the asymptotic mutual information is of independent in- terest but, as we will see, it is intimately related to estimation-theoretic quantities.

In this paper, we focus on the symmetric binary model. Namely we assume the vertex set $V=[n]\equiv\{1,2,\ \ldots,\ n\}$ to be partitioned into two sets $V=V_{+}\cup V_{-}$, with $\mathbb{P}(i\in V_{+})= \mathbb{P}(i\in V_{-})=1/2$ independently across vertices $i$. Conditional on the edge labels, edges are independent with

View Source\begin{equation*}\mathbb{P}((i,\ j)\in E\vert V_{+}, V_{-})=\begin{cases} p_{n} & \mathrm{i}\mathrm{f}\ \{i,\ j\}\subseteq V_{+}\ \mathrm{o}\mathrm{r}\ V_{-}\\ q_{n} & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{cases} \tag{1}\end{equation*}

Throughout we will denote by $\boldsymbol{X}=(X_{i})_{i\in V}$ the set of vertex labels $X_{i}\in\{+1,\ -1\}$, and we will be interested in the conditional entropy $H(\boldsymbol{X}\vert \boldsymbol{G})$ or-equivalently– the mutual information $I(\boldsymbol{X};\boldsymbol{G})$ in the limit $n\rightarrow\infty$. We will write $\boldsymbol{G}\sim \mathrm{SBM}(n;p,\ q)$ (or $(X,\ G)\sim SBM (n;p,\ q)$) to imply that the graph $G$ is distributed according to the stochastic block model with $n$ vertices and parameters $p, q$.

Since we are interested in the large $n$ behavior, two preliminary remarks are in order:

1. Normalization. We obviously have¹$0\leq H(X\vert G)\leq n$ log 2. It is therefore natural to study the per-vertex entropy $H(X\vert G)/n$. As we will see, depending on the model parameters, this will take a value between 0 and $\log 2$.

2. Scaling. The reconstruction problem becomes easier when $p_{n}$ and $q_{n}$ are well separated, and more difficult when they are closer to each other. For instance, in an early contribution, Dyer and Frieze [2] proved that the labels can be reconstructed exactly –modulo an overall flip– if $p_{n}=p > q_{n}=(1$ are distinct and independent of $n$. In particular, such exact recovery results imply that $H(X\vert G)/n\rightarrow 0$. In this regime, the ‘signal’ is so strong that the conditional entropy is trivial. Letting $\overline{p}_{n}=(p_{n}+q_{n})/2$ be the average edge probability. It turns out that the relevant ‘signal-to-noise ratio’ (SNR) is given by the following parameter:

$$\begin{equation*} \lambda_{n}=\frac{n(p_{n}-q_{n})^{2}}{4\overline{p}_{n}(1-\overline{p}_{n})}. \tag{2}\end{equation*}$$ View Source\begin{equation*} \lambda_{n}=\frac{n(p_{n}-q_{n})^{2}}{4\overline{p}_{n}(1-\overline{p}_{n})}. \tag{2}\end{equation*}

Indeed, we will see that $H(X\vert G)/n$ of order 1, and has a strictly positive limit when $\lambda_{n}$ converges to $\lambda$ of order one. In this regime, the fraction of incorrectly labeled vertices has a limit in (0, 1).

A. Main Results: Limiting Mutual Information and MMSE

Our main result provides a single-letter characterization for the per-vertex mutual information. This is given in terms of an effective Gaussian scalar channel. Namely, define the Gaussian channel

$$\begin{equation*}Y_{0}=Y_{0}(\gamma)=\sqrt{\gamma}X_{0}+Z_{0}, \tag{3}\end{equation*}$$ View Source\begin{equation*}Y_{0}=Y_{0}(\gamma)=\sqrt{\gamma}X_{0}+Z_{0}, \tag{3}\end{equation*} where $\mathrm{X}_{0} \sim\,\,\mathrm{Uniform}\,\,\,(\{+1,\ -1\})$ independent² of $Z_{0}\sim \mathrm{N}(0,1)$. We denote by $\mathsf{mmse} (\gamma)$ and $\vert (\gamma)$ the corresponding minimum mean square error and mutual information: $$\begin{align*}\vert (\gamma)=\mathbb{E}\log\{\frac{\mathrm{d}p_{Y\vert X}(Y_{0}(\gamma)\vert X_{0})}{\mathrm{d}p_{Y}(Y_{0}(\gamma))}\},&\tag{4}\\ \mathsf{mmse}(\gamma)=\mathbb{E}\{(X_{0}-\mathbb{E}\{X_{0}\vert Y_{0}(\gamma)\})^{2}\}.& \tag{5}\end{align*}$$ View Source\begin{align*}\vert (\gamma)=\mathbb{E}\log\{\frac{\mathrm{d}p_{Y\vert X}(Y_{0}(\gamma)\vert X_{0})}{\mathrm{d}p_{Y}(Y_{0}(\gamma))}\},&\tag{4}\\ \mathsf{mmse}(\gamma)=\mathbb{E}\{(X_{0}-\mathbb{E}\{X_{0}\vert Y_{0}(\gamma)\})^{2}\}.& \tag{5}\end{align*}

In the present case, these quantities can be written explicitly as Gaussian integrals of elementary functions:

$$\begin{align*}\mathsf{l}(\gamma)&=\gamma-\mathrm{E}\log\cosh(\gamma+\sqrt{\gamma}Z_{0}),\tag{6}\\ \mathsf{mmse}(\gamma)&=1-\mathrm{E}\{\tanh(\gamma+\sqrt{\gamma}Z_{0})^{2}\}. \tag{7}\end{align*}$$ View Source\begin{align*}\mathsf{l}(\gamma)&=\gamma-\mathrm{E}\log\cosh(\gamma+\sqrt{\gamma}Z_{0}),\tag{6}\\ \mathsf{mmse}(\gamma)&=1-\mathrm{E}\{\tanh(\gamma+\sqrt{\gamma}Z_{0})^{2}\}. \tag{7}\end{align*}

The following theorem gives a single-letter characterization of the limiting per-vertex mutual information.

Theorem I.1

For any $\lambda > 0$, let $\gamma_{\ast}=\gamma_{\ast}(\lambda)$ be the largest non-negative solution of the equation:

$$\begin{equation*}\gamma=\lambda(1-\mathsf{mmse}(\gamma)). \tag{8}\end{equation*}$$ View Source\begin{equation*}\gamma=\lambda(1-\mathsf{mmse}(\gamma)). \tag{8}\end{equation*}

We refer to $\gamma_{\ast}(\lambda)$ as to the effective signal-to-noise ratio. Further; define $\Psi(\gamma,\ \lambda)$ by:

$$\begin{equation*}\Psi(\gamma,\ \lambda)=\frac{\lambda}{4}+\frac{\gamma^{2}}{4\lambda}-\frac{\gamma}{2}+\vert (\gamma). \tag{9}\end{equation*}$$ View Source\begin{equation*}\Psi(\gamma,\ \lambda)=\frac{\lambda}{4}+\frac{\gamma^{2}}{4\lambda}-\frac{\gamma}{2}+\vert (\gamma). \tag{9}\end{equation*}

Let the graph $G$ and vertex labels $\boldsymbol{X}$ be distributed according to the stochastic block model with $n$ vertices and parameters $p_{n}, q_{n}(i.e. (G,\ X)\sim\mathrm{SBM}\,\,(n;p_{n},\ q_{n}))$ and define $\lambda_{n}\equiv n(p_{n}-q_{n})^{2}/(4\overline{p}_{n}(1-\overline{p}_{n}))$.

Assume that, as $n\rightarrow\infty, (i)\lambda_{n}\rightarrow\lambda$ and (ii) $n\overline{p}_{n}(1- \overline{p}_{n})\rightarrow\infty$. Then,

$$\begin{equation*}\lim_{n\rightarrow\infty}\frac{1}{n}I(\boldsymbol{X};G)=\Psi(\gamma_{\ast}(\lambda),\ \lambda)=\inf_{\gamma\in[0,\infty]}\Psi(\gamma,\ \lambda). \tag{10}\end{equation*}$$ View Source\begin{equation*}\lim_{n\rightarrow\infty}\frac{1}{n}I(\boldsymbol{X};G)=\Psi(\gamma_{\ast}(\lambda),\ \lambda)=\inf_{\gamma\in[0,\infty]}\Psi(\gamma,\ \lambda). \tag{10}\end{equation*}

This theorem and its proof has implications on the minimum error that can be achieved in estimating the labels $\boldsymbol{X}$ from the graph $\boldsymbol{G}$. For reasons that will become clear below, a natural metric is given by the matrix minimum mean square error

$$\begin{equation*}\mathrm{MMSE}_{n}(\lambda)\equiv\frac{1}{n(n-1)}\mathbb{E}\{\Vert XX^{\mathrm{T}}-\mathrm{E}\{XX^{\mathrm{T}}\vert G\}\Vert_{F}^{2}\}.\end{equation*}$$ View Source\begin{equation*}\mathrm{MMSE}_{n}(\lambda)\equiv\frac{1}{n(n-1)}\mathbb{E}\{\Vert XX^{\mathrm{T}}-\mathrm{E}\{XX^{\mathrm{T}}\vert G\}\Vert_{F}^{2}\}.\end{equation*}

Theorem I.2

Under the assumptions of Theorem I.1 (in particular assuming $\lambda_{n}\rightarrow\lambda$ as $n\rightarrow\infty$), the following limit holds for the matrix minimum mean square error

$$\begin{equation*}\lim_{n\rightarrow\infty}\mathrm{MMSE}_{n}(\lambda_{n})=1-\frac{\gamma_{\ast}(\lambda)^{2}}{\lambda^{2}}. \tag{12}\end{equation*}$$ View Source\begin{equation*}\lim_{n\rightarrow\infty}\mathrm{MMSE}_{n}(\lambda_{n})=1-\frac{\gamma_{\ast}(\lambda)^{2}}{\lambda^{2}}. \tag{12}\end{equation*}

Further, this implies $\lim_{n\rightarrow\infty}\mathsf{MMSE}_{n}(\lambda_{n})$ = for $\lambda\leq 1$ and $\lim_{n\rightarrow\infty}\mathsf{MMSE}_{n}(\lambda_{n}) <$ for $\lambda > 1$.

A couple of remarks are in order

Remark I.3

Notice that our assumptions require $n\overline{p}_{n}(1- \overline{p}_{n}) \rightarrow\infty$ at any, arbitrarily slow, rate. In words, this corresponds to the graph average degree diverging at any, arbitrarily slow, rate. Recently (see Section II for a discussion of this literature), there has been considerable interest in the case of bounded average degree, namely

$$\begin{equation*}p_{n}=\frac{\alpha}{n},\qquad q_{n}=\frac{b}{n}, \tag{13}\end{equation*}$$ View Source\begin{equation*}p_{n}=\frac{\alpha}{n},\qquad q_{n}=\frac{b}{n}, \tag{13}\end{equation*} with $\alpha, b$ bounded. Our proof gives an explicit error bound in terms of problem parameters even when $n\overline{p}_{n}(1-\overline{p}_{n})$ is of order one. Hence we are able to characterize the asymptotic mutual information for large-but-bounded average degree up to an offset: $$\begin{equation*}\mathop{\lim\sup}_{n\rightarrow\infty}\left\vert \frac{1}{n}I(X;G)-\Psi(\gamma_{\ast}(\lambda),\ \lambda)\right\vert \leq\frac{C\lambda^{3}}{\sqrt{\alpha+b}}, \tag{14}\end{equation*}$$ View Source\begin{equation*}\mathop{\lim\sup}_{n\rightarrow\infty}\left\vert \frac{1}{n}I(X;G)-\Psi(\gamma_{\ast}(\lambda),\ \lambda)\right\vert \leq\frac{C\lambda^{3}}{\sqrt{\alpha+b}}, \tag{14}\end{equation*}

Further, our mild condition on diverging average degree should be contrasted with the phase transition of naive spectral methods. It is well understood that the community structure can be estimated by the principal eigenvector of the centered adjacency matrix $\boldsymbol{G}-\mathrm{E}\{\boldsymbol{G}\}=(\boldsymbol{G}-\overline{p}_{n}11^{\mathrm{T}})$. (We denote by $\boldsymbol{G}$ the graph as well as its adjacency matrix.) This approach is successful for $\lambda > 1$ but requires average degree $n\overline{p}_{n}\geq(\log n)^{c}$ for $c$ a constant [7], [8].

Remark I.4

The reader will notice that the limiting expres- sions for the mutual information and MMSE are related by the identity:

$$\begin{equation*}\frac{\mathrm{d}\Psi(\gamma_{\ast}(\lambda),\lambda)}{\mathrm{d}\lambda}=\frac{1}{4}\left(1-\frac{\gamma_{\ast}(\lambda)^{2}}{\lambda^{2}}\right). \tag{15}\end{equation*}$$ View Source\begin{equation*}\frac{\mathrm{d}\Psi(\gamma_{\ast}(\lambda),\lambda)}{\mathrm{d}\lambda}=\frac{1}{4}\left(1-\frac{\gamma_{\ast}(\lambda)^{2}}{\lambda^{2}}\right). \tag{15}\end{equation*}

Such an identity relating mutual information and MMSE is well-known for estimation in Gaussian noise [9], and its appearance in the setting of the SBM is a priori surprising. However, it is hardly coincidental, as our proof strategy involves reducing the SBM to an analogous “Gaussian noise” setting (see Section III).

The rest of the paper is organized as follows. We discuss related work on the stochastic block model in Section II. In Section III, we discuss some consequences of our main results for other estimation metrics. Finally, in Section IV, we outline our proof strategy. We refer the reader to the full version [10] for proofs of the results.

The stochastic block model was first introduced within the social science literature in [1]. Around the same time, it was studied within theoretical computer science [11], [2], [12], under the name of 'planted partition model. A large part of the literature has focused on the problem of exact recovery, providing algorithms and conditions on the gap between $p_{n}$ and $q_{n}$ that guarantee exact recovery of the vertex labels (up to a sign flip), with phase transitions recently discovered [13]–[14][15]. On the other hand, recent works have also studied the detection problem, i.e., recovering a positively correlated community structure. This was highlighted by [16], who conjectured the following intriguing phase transition phenomenon: the detection problem is solvable if and only if $(\alpha-b)^{2} > 2(\alpha+b)$ where $p_{n}=\alpha/n$ and $q_{n}=b/n$. The two parts of the conjecture were settled in [17] and [18], [19] respectively. Results for detection with more than two communities were also obtained in [20], [21], [15], [22].

In a sense, the present paper bridges detection and exact recovery, by characterizing the minimum estimation error when this is non-zero, but —for $\lambda > 1$-smaller than for random guessing. Note that [23] introduced an information-theoretic view of the SBM, showing that $I(\boldsymbol{X;G})/n$ admits a limit as $n\rightarrow\infty$, when $p_{n}=\alpha/n\leq q_{n}=b/n$. The key argument establishes a certain sub-additivity property for the conditional entropy $H(\boldsymbol{X;G})$. While these techniques might extend to a broad family of planted models, the sub-additivity property does not establish the limiting value itself.

In terms of proof techniques, our arguments are closest to [24], [25]. We use the well-known Lindeberg strategy to reduce computation of mutual information in the SBM to mutual information of the Gaussian observation model. We then compute the latter mutual information by developing sharp algorithmic upper bounds, which are then shown to be asymptotically tight via an area theorem. The Lindeberg strategy builds from [24], [26] while the area theorem argument also appeared in [27].

Lesieur, Krzakala and Zdeborová [28] studied estimation of low-rank matrices observed through noisy memoryless channels. They conjectured that the resulting minimal estimation error is universal across a variety of channel models. Our proof establishes universality across two such models: the Gaussian and the binary output channels. We expect that similar techniques can be useful to prove universality for other models as well.

Finally, we expect that the result obtained in this paper are likely to extend to more general models, such as censored or labelled models [23], [29], [30], [31], [21].

Theorem I.2 establishes that a phase transition takes place at $\lambda = 1$ for the matrix minimum mean square error $\mathsf{MMSE}_{n}(\lambda_{n})$ defined in Eq. (11). Throughout this section, we will omit the subscript $n$ to denote the $n\rightarrow\infty$ limit (for instance, we write $\mathsf{MMSE}(\lambda)\equiv\lim_{n\rightarrow\infty}\mathsf{MMSE}_{n}(\lambda_{n}))$.

Fig. 1:

Illustration of the fixed point equation eq. (8). The ‘effective signal-to-noise ratio’ $\gamma_{\ast}(\lambda)$ is given by the intersection of the curve $\gamma\rightarrow G(\gamma)=1-\mathrm{mmse}(\gamma)$, and the line $\gamma/\lambda$.

View All

Fig. 2:

Left frame: asymptotic mutual information per vertex of the two-groups stochastic block model, as a function of the signal-to-noise ratio $\lambda$. The dashed lines are simple upper bounds (see [10]): $\lim_{n\rightarrow\infty}I(\boldsymbol{X;G})/n\leq\lambda/4$ and $I(\boldsymbol{X;G})/n\leq\log 2$. Right frame: asymptotic estimation error under different metrics. Note the phase transition at $\lambda=1$ in both frames.

View All

Figure 2 reports the asymptotic prediction for $\mathsf{MMSE}(\lambda)$ stated in Theorem I.2, and evaluated as discussed above. The error decreases rapidly to 0 for $\lambda > 1$.

In this section we discuss two other estimation metrics. In both cases we define these metrics by optimizing a suitable risk over a class of estimators: it is understood that randomized estimators are admitted as well.

View Source\begin{equation*}\mathsf{vmmse}_{n}(\lambda_{n})=\frac{1}{n}\inf_{\hat{x}\mathcal{G}_{n}\rightarrow \mathbb{R}^{n}}\mathrm{E}\{\min_{s\in\{\pm 1\}}\Vert \boldsymbol{X}-s\hat{\boldsymbol{x}}(\boldsymbol{G})\Vert_{2}^{2}\}.\tag{16}\end{equation*}

• The first metric is the vector minimum mean square error:

• Note the minimization over the sign $s$: this is necessary because the vertex labels can be estimated only up to an overall flip. Of course $\mathsf{vmmse}_{n}(\lambda_{n})\in[0,1]$, since it is always possible to achieve vector mean square error equal to one by returning $\hat{x}(\boldsymbol{G})=0$. • The second metric is the overlap:

$$\begin{equation*}\mathop{Overlap}=_{n}(\lambda_{n})=\frac{1}{n}\sup_{\hat{s}.\mathcal{G}_{n}\rightarrow\{\pm 1\}^{n}}\mathbb{E}\{\vert \langle \boldsymbol{X},\hat{s}(\boldsymbol{G})\}\vert \}. \tag{17}\end{equation*}$$ View Source\begin{equation*}\mathop{Overlap}=_{n}(\lambda_{n})=\frac{1}{n}\sup_{\hat{s}.\mathcal{G}_{n}\rightarrow\{\pm 1\}^{n}}\mathbb{E}\{\vert \langle \boldsymbol{X},\hat{s}(\boldsymbol{G})\}\vert \}. \tag{17}\end{equation*}

Again Overlap $n(\lambda_{n})\in[0,1]$ (but now large overlap corresponds to good estimation). Indeed by returning $\hat{x}_{r}(\boldsymbol{G})\in\{+1,\ -1\}$ uniformly at random, we obtain $\mathbb{E}\{\vert \langle \boldsymbol{X},\hat{s}(\boldsymbol{G})\}\vert \}/n=O(n^{-1/2})\rightarrow0$.

Note that the main difference between overlap and vector minimum mean square error is that in the latter case we consider estimators $\hat{x}:\mathcal{G}_{n}\rightarrow \mathbb{R}^{n}$ taking arbitrary real values, while in the former we assume estimators $\hat{s}:\mathcal{G}_{n}\rightarrow\{+1,\ -1\}^{n}$ taking binary values.

The next lemma clarifies the relationship between matrix, vector minimum mean square error and the overlap.

III.

Lemma III.1

With the above definitions, we have

$$\begin{align*}&\mathsf{vmmse}_{n}(\lambda)\geq 1-\sqrt{1-(1-n^{-1})\mathsf{MMSE}_{n}(\lambda)},\tag{18}\\ &\mathsf{vmmse}_{n}(\lambda)\leq \mathsf{MMSE}_{n}(\lambda),\tag{19}\\ &\mathsf{Overlap}_{n}(\lambda)\leq\sqrt{1-\mathsf{MMSE}_{n}(\lambda)},\tag{20}\\ &\mathsf{Overlap}_{n}(\lambda)\geq 1-\mathsf{MMSE}_{n}(\lambda). \tag{21}\end{align*}$$ View Source\begin{align*}&\mathsf{vmmse}_{n}(\lambda)\geq 1-\sqrt{1-(1-n^{-1})\mathsf{MMSE}_{n}(\lambda)},\tag{18}\\ &\mathsf{vmmse}_{n}(\lambda)\leq \mathsf{MMSE}_{n}(\lambda),\tag{19}\\ &\mathsf{Overlap}_{n}(\lambda)\leq\sqrt{1-\mathsf{MMSE}_{n}(\lambda)},\tag{20}\\ &\mathsf{Overlap}_{n}(\lambda)\geq 1-\mathsf{MMSE}_{n}(\lambda). \tag{21}\end{align*}

As an immediate corollary of these lemmas (together with Theorem I.2), we obtain that $\lambda=1$ is the critical point for other estimation metrics as well.

In this section we describe the main elements used in the proof of Theorems I.1 and I.2. As an intermediate step, we introduce the Gaussian observation model:

View Source\begin{equation*}\boldsymbol{Y}=\sqrt{\frac{\lambda}{n}}\boldsymbol{XX}^{\top}+\boldsymbol{Z}, \tag{27}\end{equation*}

Our strategy consists of two main steps:

1. Show that the mutual information in the SBM and the Gaussian observation model (i.e. $I(\boldsymbol{X;G})$ and $I(\boldsymbol{X;Y}))$ coincide to leading order.

2. Prove an asymptotic characterization of the mutual information $I(\boldsymbol{X;Y})$ via an appropriately defined approximate message passing (AMP) algorithm.

The first step is established in the following proposition that also gives explicit error bounds on the difference between the two mutual information terms.

IV.

Proposition IV.1

Assume that, as $n\rightarrow\infty, (i)\lambda_{n}\rightarrow\lambda$ and (ii) $n\overline{p}_{n}(1-\overline{p}_{n})\rightarrow\infty$. Then there is a constant $C$ independent of $n$ such that

$$\begin{equation*}\frac{1}{n}\vert I(\boldsymbol{X;G})-I(\boldsymbol{X;Y})\vert \leq\frac{C\lambda^{3/2}}{\sqrt{n\overline{p}_{n}(1-\overline{p}_{n})}}+C\vert \lambda_{n}-\lambda\vert. \tag{28}\end{equation*}$$ View Source\begin{equation*}\frac{1}{n}\vert I(\boldsymbol{X;G})-I(\boldsymbol{X;Y})\vert \leq\frac{C\lambda^{3/2}}{\sqrt{n\overline{p}_{n}(1-\overline{p}_{n})}}+C\vert \lambda_{n}-\lambda\vert. \tag{28}\end{equation*}

The proof of this proposition relies on the celebrated Lindeberg method, whereby we replace the non-Gaussian random variables $G_{ij}$ with Gaussian counterparts $Y_{ij}$ and control the error incurred. Similar arguments have been used to establish universality of various macroscopic properties across microscopic details of the underlying probabilistic models (see [24], [26] for applications to compressed sensing, information theory and spin glass theory).

The second step of characterizing the Gaussian model of Eq.(27) involves developing algorithmic upper bounds via an appropriately defined Approximate Message Passing algorithm. This algorithm yields estimates of $\boldsymbol{XX}^{\top}$, and a corresponding mean squared error $\mathsf{MSE}_{\mathrm{AMP}}(\lambda)$ incurred by these estimates. This mean squared error is shown to be sharp, via an area theorem argument and the I-MMSE identity. Such an area theorem argument has been used in coding theory [32], multiuser detection [27] and sparse PCA [25]. Finally we state the characterization of the Gaussian model, since it is of independent interest.

IV.

Theorem IV.2

For any $\lambda > 0$, let $\gamma_{\ast}(\lambda)$ be the largest non- negative solution of the equation:

$$\begin{equation*}\gamma=\lambda(1-\mathrm{mmse}(\gamma)). \tag{29}\end{equation*}$$ View Source\begin{equation*}\gamma=\lambda(1-\mathrm{mmse}(\gamma)). \tag{29}\end{equation*}

Further, define $\Psi(\gamma,\ \lambda)$ by:

View Source\begin{equation*}\Psi(\gamma,\ \lambda)=\frac{\lambda}{4}+\frac{\gamma^{2}}{4\lambda}-\frac{\gamma}{2}+\vert (\gamma). \tag{30}\end{equation*}

Then, we have

View Source\begin{equation*}\lim_{n\rightarrow\infty}\frac{1}{n}I(\boldsymbol{X;Y})=\Psi(\gamma_{\ast}(\lambda),\ \lambda). \tag{31}\end{equation*}