Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

Introduction and main results

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 [HLL83, DF89, SN97, CK99, ABFX08]. 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 [HLL83]. For other data-mining applications, they represent latent attributes of the nodes [McS01]. 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 asymptotically for large networks under suitable conditions on the model parameters. The asymptotic mutual information is of independent interest, but is also intimately related to estimation-theoretic quantities.

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}}|{\boldsymbol{G}})$ or –equivalently– the mutual information $I({\boldsymbol{X}};{\boldsymbol{G}})$ in the limit $n\to\infty$. We will write ${\boldsymbol{G}}\sim{\rm SBM}(n;p,q)$ (or $({\boldsymbol{X}},{\boldsymbol{G}})\sim{\rm 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:

Normalization. We obviously haveUnless explicitly stated otherwise, logarithms will be in base $e$, and entropies will be measured in nats. $0\leq H({\boldsymbol{X}}|{\boldsymbol{G}})\leq n\,\log 2$. It is therefore natural to study the per-vertex entropy $H({\boldsymbol{X}}|{\boldsymbol{G}})/n$.

As we will see, depending on the model parameters, this will take any value between and $\log 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 [DF89] proved that the labels can be reconstructed exactly –modulo an overall flip– if $p_{n}=p>q_{n}=q$ are distinct and independent of $n$. This –in particular– implies $H({\boldsymbol{X}}|{\boldsymbol{G}})/n\to 0$ in this limit (in fact, it implies $H({\boldsymbol{X}}|{\boldsymbol{G}})\to\log 2$). In this regime, the ‘signal’ is so strong that the conditional entropy is trivial. Indeed, recent work [ABH14, MNS14a] show that this can also happen with $p_{n}$ and $q_{n}$ vanishing, and characterizes the sequences $(p_{n},q_{n})$ for which this happens. (See Section 2 for an account of related work.)

Let $\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:

Indeed, we will see that $H({\boldsymbol{X}}|{\boldsymbol{G}})/n$ of order $1$, and has a strictly positive limit when $\lambda_{n}$ is of order one. This is also the regime in which the fraction of incorrectly labeled vertices has a limit that is strictly between and $1$.

As mentioned above, 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

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

We are now in position to state our main result.

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

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

Let the graph ${\boldsymbol{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. $({\boldsymbol{G}},{\boldsymbol{X}})\sim{\rm 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\to\infty$, $(i)$ $\lambda_{n}\to\lambda$ and $(ii)$ $n\overline{p}_{n}(1-\overline{p}_{n})\to\infty$. Then,

Of course, we could have stated our result in terms of conditional entropy. Namely

Notice that our assumptions require $n\overline{p}_{n}(1-\overline{p}_{n})\to\infty$ at any, arbitrarily slow, rate. In words, this corresponds to the graph average degree diverging at any, arbitrarily slow, rate.

Recently (see Section 2 for a discussion of this literature), there has been considerable interest in the case of bounded average degree, namely

with $a,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 that vanishes with the average degree.

Our main result 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

(Occasionally, we will also use the notation ${\sf MMSE}(\lambda;n)$ for ${\sf MMSE}_{n}(\lambda)$.) Using the exchangeability of the indices $\{1,\dots,n\}$, this can also be rewritten as

(Here $\mathcal{G}_{n}$ denotes the set of graphs with vertex set $[n]$.) In words, ${\sf MMSE}_{n}(\lambda)$ is the minimum error incurred in estimating the relative sign of the labels of two given (distinct) vertices. Equivalently, we can assume that vertex $1$ has label $X_{1}=+1$. Then ${\sf MMSE}_{n}(\lambda)$ is the minimum mean square error incurred in estimating the label of any other vertex, say vertex $2$. Namely, by symmetry, we have (see Section 3)

In particular ${\sf MMSE}_{n}(\lambda)\in$, with ${\sf MMSE}_{n}(\lambda)\to 1$ corresponding to random guessing.

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

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

For further discussion of this result and its generalizations, we refer to Section 3. In particular, Corollary 3.7 establishes that $\lambda=1$ is a phase transition for other estimation metrics as well, in particular for overlap and vector mean square error.

As Theorem 1.1, also the last theorem holds under the mild condition that the average degree $n\overline{p}_{n}$ diverges at any, arbitrarily slow rate. This should be contrasted with the phase transition of naive spectral methods.

Our proof of Theorem 1.1 and Theorem 1.4 involves the analysis of a Gaussian observation model, whereby the rank one matrix ${\boldsymbol{X}}{\boldsymbol{X}}^{{\sf T}}$ is corrupted by additive Gaussian noise, according to ${\boldsymbol{Y}}=\sqrt{\lambda/n}{\boldsymbol{X}}{\boldsymbol{X}}^{\sf T}+{\boldsymbol{Z}}$. In particular, we prove a single letter characterization of the asymptotic mutual information per dimension in this model $\lim_{n\to\infty}I({\boldsymbol{X}};{\boldsymbol{Y}})$, cf. Theorem 4.3 below. The resulting asymptotic value is proved to coincide with the asymptotic value in the stochastic block model, as established in Theorem 1.1. In other words, the per-dimension mutual information turns out to be universal across multiple noise models.

2 Outline of the paper

In Section 2 we review the literature on this problem. We then discuss the connection with estimation in Section 3. This section also demonstrates how to evaluate the asymptotic formula in Theorem 1.1.

Section 4 describes the proof strategy. As an intermediate step, we introduce a Gaussian observation model which is of independent interest. The proof of Theorem 1.1 is reduced to two main propositions:

Proposition 4.1 establishes that –within the regime defined in Theorem 1.1– the stochastic block model is asymptotically equivalent to the Gaussian observation model (see Section 4 for a formal definition). This statement (with explicit error bounds) is proved in Section 5 through a careful application of the Lindeberg method.

Proposition 4.2 develops a single-letter characterization of the asymptotic per-vertex mutual information of the Gaussian observation model. The proof of this fact is presented in Section 6 and builds on two steps. We first prove an asymptotic upper bound on the matrix minimum mean square error ${\sf MMSE}_{n}(\lambda)$ using an approximate message passing (AMP) algorithm. We then use an area theorem to prove that this upper bound is tight.

Finally, Section 7 contains the proof of Theorem 1.4. Several technical details are deferred to the appendices.

3 Notations

The set of first $n$ integers is denoted by $[n]=\{1,2,\dots,n\}$.

When possible, we will follow the convention of denoting random variables by upper-case letters (e.g. $X,Y,Z,\dots$), and their values by lower case letters (e.g. $x,y,z,\dots$). We use boldface for vectors and matrices, e.g. ${\boldsymbol{X}}$ for a random vector and ${\boldsymbol{x}}$ for a deterministic vector. The graph ${\boldsymbol{G}}$ will be identified with its adjacency matrix. Namely, with a slight abuse of notation, we will use ${\boldsymbol{G}}$ both to denote a graph ${\boldsymbol{G}}=(V=[n],E)$ (with $V=[n]$ the vertex set, and $E$ the edge set, i.e. a set of unordered pairs of vertices), and its adjacency matrix. This is a symmetric zero-one matrix ${\boldsymbol{G}}=(G_{ij})_{1\leq i,j\leq n}$ with entries

Throughout we assume $G_{ii}=0$ by convention.

We write $f_{1}(n)=f_{2}(n)+O(f_{3}(n))$ to mean that $\left\lvert{f_{1}(n)-f_{2}(n)}\right\rvert\leq Cf_{3}(n)$ for a universal constant $C$. We denote by $C$ a generic (large) constant that is independent of problem parameters, whose value can change from line to line.

We say that an event holds with high probability if it holds with probability converging to one as $n\to\infty$.

Unless stated otherwise, logarithms will be taken in the natural basis, and entropies measured in nats.

Related work

The stochastic block model was first introduced within the social science literature in [HLL83]. Around the same time, it was studied within theoretical computer science [BCLS87, DF89], under the name of ‘planted partition model. ’

A large part of the literature has focused on the problem of exact recovery of the community (cluster) structure. A long series of papers [BCLS87, DF89, Bop87, SN97, JS98, CK99, CI01, McS01, BC09, RCY11, CWA12, CSX12, Vu14, YC14], establishes sufficient conditions on the gap between $p_{n}$ and $q_{n}$ that guarantee exact recovery of the vertex labels with high probability. A sharp threshold for exact recovery was obtained in [ABH14, MNS14a], showing that for $p_{n}=\alpha\log(n)/n$, $q_{n}=\beta\log(n)/n$, $\alpha,\beta>0$, exact recovery is solvable (and efficiently so) if and only if $\sqrt{\alpha}-\sqrt{\beta}\geq 2$. Efficient algorithms for this problem were also developed in [YP14, BH14, Ban15]. For the SBM with arbitrarily many communities, necessary and sufficient conditions for exact recovery were recently obtained in [AS15]. The resulting sharp threshold is efficiently achievable and is stated in terms of a CH-divergence.

A parallel line of work studied the detection problem. In this case, the estimated community structure is only required to be asymptotically positively correlated with the ground truth. For this requirement, two independent groups [Mas14, MNS14b] proved that detection is solvable (and so efficiently) if and only if $(a-b)^{2}>2(a+b)$, when $p_{n}=a/n$, $q_{n}=b/n$. This settles a conjecture made in [DKMZ11] and improves on earlier work [Co10]. Results for detection with more than two communities were recently obtained in [GV14, CRV15, AS15, BLM15]. A variant of community detection with a single hidden community in a sparse graph was studied in [Mon15].

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.

An information-theoretic view of the SBM was first introduced in [AM13, AM15]. There it was shown that in the regime of $p_{n}=a/n$, $q_{n}=b/n$, and $a\leq b$ (i.e., disassortative communities), the normalized mutual information $I({\boldsymbol{X}};{\boldsymbol{G}})/n$ admits a limit as $n\to\infty$. This result is obtained by showing that the condition entropy $H({\boldsymbol{X}}|{\boldsymbol{G}})$ is sub-additive in $n$, using an interpolation method for planted models. While the result of [AM13, AM15] holds for arbitrary $a\leq b$ (possibly small) and extend to a broad family of planted models, the existence of the limit in the assortative case $a>b$ is left open. Further, sub-additivity methods do not provide any insight as to the limit value.

For the partial recovery of the communities, it was shown in [MNS14a] that the communities can be recovered up to a vanishing fraction of the nodes if and only if $n(p-q)^{2}/(p+q)$ diverges. This is generalized in [AS15] to the case of more than two communities. In these regimes, the normalized mutual information $I({\boldsymbol{X}};{\boldsymbol{G}})/n$ (as studied in this paper) tends to $\log 2$ nats. For the constant degree regime, it was shown in [MNS13] that when $(a-b)^{2}/(a+b)$ is sufficiently large, the fraction of nodes that can be recovered is determined by the broadcasting problem on tree [EKPS00]. Namely, consider the reconstruction problem whereby a bit is broadcast on a Galton-Watson tree with Poisson($(a+b)/2$) offspring and with binary symmetric channels of bias $b/(a+b)$ on each branch. Then the probability of recovering the bit correctly from the leaves at large depth gives the fraction of nodes that can be correctly labeled in the SBM.

In terms of proof techniques, our arguments are closest to [KM11, DM14]. 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 [KM11, Cha06] while the area theorem argument also appeared in [MT06]. We expect these techniques to be more broadly applicable to compute quantities like normalized mutual information or conditional entropy in a variety of models.

Let us finally mentioned that the result obtained in this paper are likely to extend to more general SBMs, with multiple communities, to the Censored Block Model studied in [AM15, ABBS14a, HG13, CHG14, CG14, ABBS14b, GRSY14, BH14, CRV15, SKLZ15], the Labeled Block Model [HLM12, XLM14], and other variants of block models. In particular, it would be interesting to understand which estimation-theoretic quantities appear for these models, and whether a general result stands behind the case of this paper.

While this paper was in preparation, Lesieur, Krzakala and Zdborová [LKZ15] 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 (see Section 4 below) 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.

Estimation phase transition

In this section we discuss how to evaluate the asymptotic formulae in Theorem 1.1 and Theorem 1.4. We then discuss the consequences of our results for various estimation metrics.

Before passing to these topics, we will derive a simple upper bound on the per-vertex mutual information, which will be a useful comparison for our results.

It is instructive to start with an elementary upper bound on $I({\boldsymbol{X}};{\boldsymbol{G}})$.

Assume $p_{n}$, $q_{n}$ satisfy the assumptions of Theorem 1.1 (in particular $(i)$ $\lambda_{n}\to\lambda$ and $(ii)$ $n\overline{p}_{n}(1-\overline{p}_{n})\to\infty$). Then

where $(a)$ follows since $\{G_{ij}\}_{i<j}$ are conditionally independent given ${\boldsymbol{X}}$ and $(b)$ because $G_{ij}$ only depends on ${\boldsymbol{X}}$ through the product $X_{i}\cdot X_{j}$ (notice that there is no comma but product in $H(G_{ij}|X_{i}\cdot X_{j})$.

The claim follows by substituting $p_{n}=\overline{p}_{n}+\sqrt{\overline{p}_{n}(1-\overline{p}_{n})\lambda_{n}/n}$, $q_{n}=\overline{p}_{n}-\sqrt{\overline{p}_{n}(1-\overline{p}_{n})\lambda_{n}/n}$ and by Taylor expansionIndeed Taylor expansion yields the stronger result $n^{-1}I({\boldsymbol{X}};{\boldsymbol{G}})\leq(\lambda_{n}/4)+n^{-1}$ for all $n$ large enough.. ∎

2 Evaluation of the asymptotic formula

Our asymptotic expression for the mutual information, cf. Theorem 1.1, and for the estimation error, cf. Theorem 1.4, depends on the solution of Eq. (8) which we copy here for the reader’s convenience:

The effective signal-to-noise ratio $\gamma_{*}(\lambda)$ that enters Theorem 1.1 and Theorem 1.4 is the largest non-negative solution of Eq. (8). This equation is illustrated in Figure 1.

It is immediate to show from the definition (29) that $G(\,\cdot\,)$ is continuous on $[0,\infty)$ with $G(0)=0$, and $\lim_{\gamma\to\infty}G(\gamma)=1$. This in particular implies that $\gamma=0$ is always a solution of Eq. (8). Further, since ${\sf mmse}(\gamma)$ is monotone decreasing in the signal-to-noise ratio $\gamma$, $G(\gamma)$ is monotone increasing. As shown in the proof of Remark 6.1 (see Appendix B.2), $G(\,\cdot\,)$ is also strictly concave on $[0,\infty)$. This implies that Eq. (8) as at most one solution in $(0,\infty)$, and a strictly positive solution only exists if $\lambda G^{\prime}(0)=\lambda>1$.

We summarize these remarks below, and refer to Figure 2 for an illustration.

The effective SNR, and the asymptotic expression for the per-vertex mutual information in Theorem 1.1 have the following properties:

For $\lambda\leq 1$, we have $\gamma_{*}(\lambda)=0$ and $\Psi(\gamma_{*}(\lambda),\lambda)=\lambda/4$.

For $\lambda\leq 1$, we have $\gamma_{*}(\lambda)\in(0,\lambda)$ strictly with $\gamma_{*}(\lambda)/\lambda\to 1$ as $\lambda\to\infty$.

Further, $\Psi(\gamma_{*}(\lambda),\lambda)<\lambda/4$ strictly with $\Psi(\gamma_{*}(\lambda),\lambda)\to\log 2$ as $\gamma\to\infty$.

All of the claims follow immediately form the previous remarks, and simple calculus, except the claim $\Psi(\gamma_{*}(\lambda),\lambda)<\lambda/4$ for $\lambda>1$. This is direct consequence of the variational characterization established below. ∎

We next give an alternative (variational) characterization of the asymptotic formula which is useful for proving bounds.

Under the assumptions and definitions of Theorem 1.1, we have

The function $\gamma\mapsto\Psi(\gamma,\lambda)$ is differentiable on $[0,\infty)$ with $\Psi(\gamma,\lambda)=\gamma^{2}/(4\lambda)+O(\gamma)\to\infty$ as $\gamma\to\infty$. Hence, the $\min_{\gamma\in[0,\infty)}\,\Psi(\gamma,\lambda)$ is achieved at a point where the first derivative vanishes (or, eventually, at ). Using the I-MMSE relation [GSV05], we get

Hence the minimizer is a solution of Eq. (8). As shown above, for $\lambda\leq 1$, the only solution is $\gamma_{*}(\lambda)=0$, which therefore yields $\Psi(\gamma_{*}(\lambda),\lambda)=\min_{\gamma\in[0,\infty)}\,\Psi(\gamma,\lambda)$ as claimed.

For $\lambda>1$, Eq. (8) admits the two solutions: and $\gamma_{*}(\lambda)>0$. However, by expanding Eq. (31) for small $\gamma$, we obtain $\Psi(\gamma,\lambda)=\Psi(0,\lambda)-(1-\lambda^{-1})\gamma^{2}/4+o(\gamma)$ and hence $\gamma=0$ is a local maximum, which implies the claim for $\lambda>1$ as well. ∎

We conclude by noting that Eq. (8) can be solved numerically rather efficiently. The simplest method consists is by iteration. Namely, we initialize $\gamma^{0}=\lambda$ and then iterate $\gamma^{t+1}=\lambda\,G(\gamma^{t})$. This approach was used for Figure 2.

3 Consequences for estimation

Figure 2 reports the asymptotic prediction for ${\sf MMSE}(\lambda)$ stated in Theorem 1.4, and evaluated as discussed above. The error decreases rapidly to 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.

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 ${\sf vmmse}_{n}(\lambda_{n})\in$, since it is always possible to achieve vector mean square error equal to one by returning ${\boldsymbol{\widehat{x}}}({\boldsymbol{G}})=0$.

In order to clarify the relation between various metrics, we begin by proving the alternative characterization of the matrix minimum mean square error in Eqs. (18), (19).

Letting ${\sf MMSE}_{n}(\lambda)$ be defined as per Eq. (14), we have

First note that Eq. (35) follows immediately from Eq. (34) since conditional expectation minimizes the mean square error (the conditioning only changes the prior on ${\boldsymbol{X}}$).

In order to prove Eq. (34), we start from Eq. (16). Since the prior distribution on $X_{1}$ is uniform, we have

where in the second line we used the fact that, conditional to ${\boldsymbol{G}}$, ${\boldsymbol{X}}$ is distributed as $-{\boldsymbol{X}}$. Continuing from Eq. (16), we get

The next lemma clarifies the relationship between matrix and vector minimum mean square error. Its proof is deferred to Appendix A.1.

Finally, a lemma that relates overlap and vector minimum mean square error, whose proof can be found in Appendix A.2.

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

The vector minimum mean square error and the overlap exhibit a phase transition at $\lambda=1$. Namely, under the assumptions of Theorem 1.1 (in particular, $\lambda_{n}\to\lambda$ and $n\overline{p}_{n}(1-\overline{p}_{n})\to\infty$), we have

If $\lambda\leq 1$, then estimation cannot be performed asymptotically better than without any information:

If $\lambda>1$, then estimation can be performed better than without any information, even in the limit $n\to\infty$:

Proof strategy: Theorem 1.1

In this section we describe the main elements used in the proof of Theorem 1.1:

We describe a Gaussian observation model which has asymptotically the same mutual information as the SBM introduced above.

We state an asymptotic characterization of the mutual information of this Gaussian model.

We describe an approximate message passing (AMP) estimation algorithm that plays a key role in the last characterization.

We then use these technical results (proved in later sections) to prove Theorem 1.1 in Section 4.3.

We recall that $\overline{p}_{n}=(p_{n}+q_{n})/2$. Define the gap $\Delta_{n}\equiv(p_{n}-q_{n})/2=\sqrt{\lambda_{n}\overline{p}_{n}(1-\overline{p}_{n})/n}$. We will assume for the proofs that $\lim_{n\to\infty}\lambda_{n}=\lambda>0$ (i.e. the assortative model) but the results also hold for $\lambda<0$ in an analogous fashion.

The edges $\{G_{ij}\}_{i<j}$ are conditionally independent given the vertex labels ${\boldsymbol{X}}$, with distribution:

As a first step, we compare the SBM with an alternate Gaussian observation model defined as follows. Let ${\boldsymbol{Z}}$ be a Gaussian random symmetric matrix generated with independent entries $Z_{ij}\sim{\sf N}(0,1)$ and $Z_{ii}\sim{\sf N}(0,2)$, independent of ${\boldsymbol{X}}$. Consider the noisy observations ${\boldsymbol{Y}}={\boldsymbol{Y}}(\lambda)$ defined by

Our first proposition proves that the mutual information between the vertex labels ${\boldsymbol{X}}$ and the observations agrees to leading order across the two models.

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

The proof of this result is presented in Section 5.

The next step consists in analyzing the Gaussian model (48), which is of independent interest. It turns out to be convenient to embed this in a more general model whereby, in addition to the observations ${\boldsymbol{Y}}$, we are also given observations of ${\boldsymbol{X}}$ through a binary erasure channel with erasure probability ${\boldsymbol{{\varepsilon}}}=1-{\varepsilon}$, ${\sf BEC}({\boldsymbol{{\varepsilon}}})$. We will denote by ${\boldsymbol{X}}({\varepsilon})=(X_{1}({\varepsilon}),\dots,X_{n}({\varepsilon}))$ the output of this channel, where we set $X_{i}({\varepsilon})=0$ every time the symbol is erased. Formally we have

where $B_{i}\sim{\sf Ber}({\varepsilon})$ are independent random variables, independent of ${\boldsymbol{X}}$, ${\boldsymbol{G}}$. In the special case ${\varepsilon}=0$, all of these observations are trivial, and we recover the original model.

The reason for introducing the additional observations ${\boldsymbol{X}}({\varepsilon})$ is the following. The graph ${\boldsymbol{G}}$ has the same distribution conditional on ${\boldsymbol{X}}$ or $-{\boldsymbol{X}}$, hence it is impossible to recover the sign of ${\boldsymbol{X}}$. As we will see, the extra observations ${\boldsymbol{X}}({\varepsilon})$ allow to break this trivial symmetry and we will recover the required results by continuity in ${\varepsilon}$ as the extra information vanishes.

Indeed, our next result establishes a single letter characterization of $I({\boldsymbol{X}};{\boldsymbol{Y}},{\boldsymbol{X}}({\varepsilon}))$ in terms of a recalibrated scalar observation problem. Namely, we define the following observation model for $X_{0}\sim{\rm Uniform}(\{+1,-1\})$ a Rademacher random variable:

Here $X_{0}$, $B_{0}\sim{\sf Ber}({\varepsilon})$, $Z_{0}\sim{\sf N}(0,1)$, are mutually independent. We denote by ${\sf mmse}(\gamma,{\varepsilon})$, the minimum mean squared error of estimating $X_{0}$ from $X_{0}({\varepsilon})$, $Y_{0}$, conditional on $B_{0}$. Recall the definitions (4), (5) of ${\sf I}(\gamma)$, ${\sf mmse}(\gamma)$, and the expressions (6), (7). A simple calculation yields

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

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

Using continuity in ${\varepsilon}$, the last result implies directly a limit result for the mutual information under the Gaussian model, which we single out since it is of independent interest.

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

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

2 Approximate Message Passing (AMP)

Above (and in the sequel) we extend the function $f_{t}$ to vectors by applying it component-wise, i.e. $f_{t}({\boldsymbol{x}}^{t},{\boldsymbol{X}}({\varepsilon}))=(f_{t}(x^{t}_{1},X({\varepsilon})_{1}),f_{t}(x^{t}_{2},X({\varepsilon})_{2}),\dots f_{t}(x^{t}_{n},X({\varepsilon})_{n}))$.

The AMP iteration above proceeds analogously to the usual power iteration to compute principal eigenvectors, but has an additional memory term $-{\sf b}_{t}f_{t-1}({\boldsymbol{x}}^{t-1})$. This additional term changes the behavior of the iterates in an important way: unlike the usual power iteration, there is an explicit distributional characterization of the iterates ${\boldsymbol{x}}^{t}$ in the limit of large dimension. Namely, for each time $t$ we will show that, approximately $x^{t}_{i}$ is a scaled version of the truth $X_{i}$ observed through Gaussian noise of a certain variance. We define the following two-parameters recursion, with initialization $\mu_{0}=\sigma_{0}=0$, which will be referred to as state evolution:

where expectation is with respect to the independent random variables $X_{0}\sim{\rm Uniform}(\{+1,-1\})$, $Z_{0}\sim{\sf N}(0,1)$ and $B_{0}\sim{\sf Ber}(1-{\varepsilon})$, setting $X_{0}({\varepsilon})=B_{0}X_{0}$.

The following lemma makes this distributional characterization precise. It follows from the more general result of [JM13] and we provide a proof in Appendix B.

Although the above holds for a relatively broad class of functions $f_{t}$, we are interested in the AMP algorithm for specific functions $f_{t}$. Specifically, we following sequence of functions

It is easy to see that $f_{t}$ satisfy the requirement of Lemma 4.4. We will refer to this version of AMP as Bayes-optimal AMP.

Note that the definition (66) depends itself on $\mu_{t}$ and $\sigma_{t}$ defined through Eqs. (63), (63). This recursive definition is perfectly well defined and yields

where ${\sf mmse}(\,\cdot\,)$ is given explicitly by Eq. (7).

In other words, the state evolution recursion reduces to a simple one-dimensional recursion that we can write in terms of the variable $\gamma_{t}\equiv\lambda\sigma_{t}^{2}$. We obtain

Our proof strategy uses the AMP algorithm to construct estimates that bound from above the minimum error of estimating ${\boldsymbol{X}}$ from observations ${\boldsymbol{Y}},{\boldsymbol{X}}({\varepsilon})$. However, in the limit of a large number of iterations, we show that the gap between this upper bound and the minimum estimation error vanishes via an area theorem.

More explicitly, we develop an upper bound on the matrix mean square error first introduced in Eq. (14). We generalize this in the obvious way to the Gaussian observation model:

(Note that we adopt here a slightly different normalization with respect to Eq. (14). This change is immaterial in the large $n$ limit.)

We then use AMP to construct the sequence of estimators ${\boldsymbol{\widehat{x}}}^{t}=f_{t-1}({\boldsymbol{x}}^{t-1},{\boldsymbol{X}}({\varepsilon}))$, indexed by $t\in\{1,2,\dots\}$, where $f_{t-1}$ is defined as in Eq. (66). The matrix mean squared error of this estimators will be denoted by

In the course of the proof, we will also see that these limits are well-defined, using the state evolution Lemma 4.4

3 Proof of Theorem 1.1 and Theorem 4.3

The proof is almost immediate given Propositions 4.1 and 4.2. Firstly, note that, for any ${\varepsilon}\in(0,1]$,

Since, by Proposition 4.2 $I({\boldsymbol{X}};{\boldsymbol{X}}({\varepsilon}),{\boldsymbol{Y}})/n$ has a well-defined limit as $n\to\infty$, and ${\varepsilon}>0$ is arbitrary, we have that:

It is immediate to check that $\Psi(\gamma,\lambda,{\varepsilon})$ is continuous in ${\varepsilon}\geq 0$, $\gamma\geq 0$ and $\Psi(\gamma,\lambda,0)=\Psi(\gamma,\lambda)$ as defined in Theorem 1.1. Furthermore, as ${\varepsilon}\to 0$, the unique positive solution $\gamma_{*}(\lambda,{\varepsilon})$ of Eq. (55) converges to $\gamma_{*}(\lambda)$, the largest non-negative solution to of Eq. (8), which we copy here for the readers’ convenience:

This follows from the smoothness and concavity of the function $1-{\sf mmse}(\gamma)$ (see Lemma 6.1). It follows that $\lim_{{\varepsilon}\to 0}\Psi(\gamma_{*}(\lambda,{\varepsilon}),\lambda,{\varepsilon})=\Psi(\gamma_{*}(\lambda),\lambda)$ and therefore

This proves Theorem 4.3. Theorem 1.1 follows by applying Proposition 4.1.

Proof of Proposition 4.1

Given a collection ${\boldsymbol{V}}=(V_{ij})_{i<j}$ of random variables defined on the same probability space as ${\boldsymbol{X}}$, and a non-negative real number $\lambda$, we define the following Hamiltonian and log-partition function associated with it:

Since the two distributions $p_{{\boldsymbol{Y}}|{\boldsymbol{X}}}$ and $p_{{\boldsymbol{Y}}}$ are absolutely continuous with respect to each other, we can write the above simply in terms of the ratio of (Lebesgue) densities, and we obtain:

This follows directly from the definition of mutual information:

As in Lemma 5.1 we can write this in terms of densities as:

Substituting this in the mutual information formula Eq. (93) yields the lemma. ∎

Define the random variables $\boldsymbol{\widetilde{G}}=(\widetilde{G}_{ij})_{i<j}$ as follows:

The following lemma shows that, to compute $I({\boldsymbol{X}};{\boldsymbol{G}})$ it suffices to compute the log-partition function with respect to the approximating Hamiltonian.

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

Now when $\max(\Delta_{n}/\overline{p}_{n},\Delta_{n}/(1-\overline{p}_{n}))\leq c_{0}$, for small enough $c_{0}$, we have by Taylor expansion the following approximation for $z\in[0,c_{0}]$:

We first simplify the RHS in Eq. (99). Recalling the definition of $\widetilde{G}_{ij}$:

where $\text{err}_{n}$ satisfies Eq. (100). We now use the following remark, which is a simple application of Bernstein inequality (the proof is deferred to Appendix B).

There exists a constant $C$ such that for every $n$ large enough:

Using this Remark, the error bound Eq. (100) and Eq. (103) in Lemma 5.2 yields

Substituting $\Delta_{n}=(\lambda_{n}\overline{p}_{n}(1-\overline{p}_{n})/n)^{1/2}$ gives the lemma. ∎

We now control the deviations that occur when replacing the variables $\widetilde{G}_{ij}$ with Gaussian variables $Z_{ij}\sqrt{\lambda/n}$.

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

This proof follows the Lindeberg strategy [Cha06, KM11]. We will show that:

(with the $O(\cdots)$ term uniform in ${\boldsymbol{X}}$). The claim then follows by taking expectations on both sides. Note that, by construction:

Then the partial derivatives above can be expressed as

However since $\left\lvert{x_{i}x_{j}-X_{i}X_{j}}\right\rvert\leq 2$, we obtain:

Applying Theorem 2 of [KM11] (stated below as Theorem 5.6) gives:

Here $\partial_{\lambda}$ denotes the derivative with respect to the variable $\lambda$. Thus,

Combining Eqs. (124), (127) gives Eq. (109), and the lemma follows by taking expectations on either side. ∎

We state below the Lindeberg generalization theorem for convenience:

With these in hand, we can now prove Proposition 4.1.

The proposition follows simply by combining the formulae for $I({\boldsymbol{X}};{\boldsymbol{G}}),I({\boldsymbol{X}};{\boldsymbol{Y}})$ in Lemmas 5.1, 5.3 with the approximation guarantee of Lemma 5.5. ∎

Proof of Proposition 4.2

Throughout this section we will write ${\boldsymbol{Y}}(\lambda)$ whenever we want to emphasize the dependence of the law of ${\boldsymbol{Y}}$ on the signal to noise parameter $\lambda$.

The proof of Proposition 4.2 follows essentially from a few preliminary lemmas.

We begin with some properties of the fixed point equation (55). The proof of this lemma can be found in Appendix B.2.

For any ${\varepsilon}\in$, the following properties hold for the function $\gamma\mapsto(1-{\sf mmse}(\gamma,{\varepsilon}))=(1-(1-{\varepsilon}){\sf mmse}(\gamma))$:

It satisfies the following limit behaviors

As a consequence we have the following for all ${\varepsilon}\in(0,1]$:

A non-negative solution $\gamma_{*}(\lambda,{\varepsilon})$ of Eq. (55) exists and is unique for all ${\varepsilon}>0$.

For any ${\varepsilon}>0$, the function $\lambda\mapsto\gamma_{*}(\lambda,{\varepsilon})$ is differentiable in $\lambda$.

Let $\{\gamma_{t}\}_{t\geq 0}$ be defined recursively by Eq. (71), with initialization $\gamma_{0}=0$. Then $\lim_{t\to\infty}\gamma_{t}=\gamma_{*}(\lambda,{\varepsilon})$.

We then compute the value of $\Psi(\gamma_{*}(\lambda,{\varepsilon}),\lambda,{\varepsilon})$ at $\lambda=\infty$ and $\lambda=0$.

Recall the definition of ${\sf mmse}(\gamma)$, cf. Eq. (5). Upper bounding ${\sf mmse}(\gamma)$ by the minimum error obtained by linear estimator yields, for any $\gamma\geq 0$, $0\leq{\sf mmse}(\gamma)\leq 1/(1+\gamma)$. Substituting these bounds in Eq. (55), we obtain

where the last expansion holds as $\lambda\to\infty$.

Let us now consider the limit $\lambda\to 0$, cf. claim (131). Considering Eq. (56), and using $0\leq\gamma_{*}(\lambda,{\varepsilon})\leq\lambda$, we have $(\lambda/4)+(\gamma_{*}(\lambda,{\varepsilon})^{2}/(4\lambda))-(\gamma/2)=O(\lambda)\to 0$. Further from the definition (4) it followsThis follows either by general information theoretic arguments, or else using dominated convergence in Eq. (6). that $\lim_{\gamma\to 0}{\sf I}(\gamma)=0$ thus yielding Eq. (131).

Consider next the $\lambda\to\infty$ limit of Eq. (132). In this limit Eq. (133) implies $\gamma_{*}(\lambda,{\varepsilon})=\lambda+\delta_{*}\to\infty$, where $\delta_{*}=\delta_{*}(\lambda,{\varepsilon})=O(1)$. Hence $\lim_{\lambda\to\infty}{\sf I}(\gamma_{*}(\lambda,{\varepsilon}))=\lim_{\gamma\to\infty}{\sf I}(\gamma)=\log 2$ (this follows again from the definition of ${\sf I}(\gamma)$). Further

Substituting in Eq. (56) we obtain the desired claim. ∎

The next lemma characterizes the limiting matrix mean squared error of the AMP estimates.

Let $\{\gamma_{t}\}_{t\geq 0}$ be defined recursively by Eq. (71) with initialization $\gamma_{0}=0$, and recall that $\gamma_{*}(\lambda,{\varepsilon})$ denotes the unique non-negative solution of Eq. (55).

Then the following limits hold for the AMP mean square error

Note that Eq. (137) follows from Eq. (136) using Lemma 6.1, point $(d)$. We will therefore focus on proving Eq. (136).

Since $\|{\boldsymbol{X}}\|_{2}^{2}=n$, the first term evaluates to 1. We use Lemma 4.4 to deal with the final two terms. Consider the last term $\langle{\boldsymbol{X}},{\boldsymbol{\widehat{x}}}^{t}\rangle^{2}/n^{2}$. Using Lemma 4.4 with the $\psi(x,s,r)=f_{t-1}(x,r)s$ we have, almost surely

Note also that $\left\lvert{X_{i}}\right\rvert$ and $\left\lvert{\widehat{x}^{t}_{i}}\right\rvert$ are bounded by 1, hence so is $\langle{\boldsymbol{X}},{\boldsymbol{\widehat{x}}}^{t}_{i}\rangle/n$. It follows from the bounded convergence theorem that

For every $\lambda\geq 0$ and ${\varepsilon}>0$:

It follows from the uniqueness and differentiability of $\gamma_{*}(\lambda,{\varepsilon})$ (cf. Lemma 6.1) that $\lambda\mapsto\Psi(\gamma_{*}(\lambda,{\varepsilon}),\lambda,{\varepsilon})$ is differentiable for any fixed ${\varepsilon}>0$, with derivative

The lemma follows from the fundamental theorem of calculus using Lemma 6.2 for $\lambda=0$, and Lemma 6.3, cf. Eq. (137). ∎

2 Proof of Proposition 4.2

We are now in a position to prove Proposition 4.2. We start from a simple remark, proved in Appendix

Further the asymptotic mutual information satisfies

We defer the proof of these facts to Appendix B.3.

Applying the (conditional) I-MMSE identity of [GSV05] we have

where $(a)$ follows from Remark 6.5, $(b)$ from Eq. (147) and (151), $(c)$ from (153), and $(d)$ from bounded convergence. Continuing from the previous chain we get

where $(e)$ follows from Lemma 6.3, $(f)$ from Lemma 6.4, and $(g)$ from Lemma 6.2.

We therefore have a chain of equalities, whence the inequality $(c)$ must hold with equality. Since ${\sf MMSE}(\lambda,{\varepsilon},n)\leq{\sf MSE}_{\sf AMP}(t;\lambda,{\varepsilon},n)$ for any $\lambda$, this implies

for almost every $\lambda$. The conclusion follows for every $\lambda$ by the monotonicity of $\lambda\mapsto{\sf MMSE}(\lambda,{\varepsilon},n)$, and the continuity of ${\sf MSE}_{\sf AMP}(\lambda,{\varepsilon})$.

Using again Remark 6.5, and the last display, we get that the following limit exists

where we used Lemma 6.4 in the last step. This concludes the proof.

Proof of Theorem 1.4

In this section we recall a general formula to compute the derivative of the conditional entropy $H({\boldsymbol{X}}|{\boldsymbol{G}})$ with respect to noise parameters. The formula was proved in [MMRU04] and [MMRU09, Lemma 2]. We restate it in the present context and present a self-contained proof for the reader’s convenience.

We consider the following setting. For $n$ an integer, denote by $\binom{[n]}{2}$ the set of unordered pairs in $[n]$ (in particular $|\binom{[n]}{2}|=\binom{n}{2})$). We will use $e,e_{1},e_{2},\dots$ to denote elements of $\binom{[n]}{2}$. For for each $e=(i,j)$ we are given a one-parameter family of discrete noisy channels indexed by $\theta\in J$ (with $J=(a,b)$ a non-empty interval), with input alphabet $\{+1,-1\}$ and finite output alphabet ${\mathcal{Y}}$. Concretely, for any $e$, we have a transition probability

We then consider ${\boldsymbol{X}}=(X_{1},X_{2},\dots,X_{n})$ a random vector in $\{+1,-1\}^{n}$, and ${\boldsymbol{Y}}=(Y_{ij})_{(i,j)\in\binom{[n]}{2}}$ a set of observations in ${\mathcal{Y}}^{\binom{[n]}{2}}$ that are conditionally independent given ${\boldsymbol{X}}$. Further $Y_{ij}$ is the noisy observation of $X_{i}X_{j}$ through the channel $p_{ij}(\,\cdot\,|\,\cdot\,)$. In formulae, the joint probability density function of ${\boldsymbol{X}}$ and ${\boldsymbol{Y}}$ is

This obviously include the two-groups stochastic block model as a special case, if we take $p_{{\boldsymbol{X}}}(\,\cdot\,)$ to be the uniform distribution over $\{+1,-1\}^{n}$, and output alphabet ${\mathcal{Y}}=\{0,1\}$. In that case ${\boldsymbol{Y}}={\boldsymbol{G}}$ is just the adjacency matrix of the graph.

In the following we write ${\boldsymbol{Y}}_{-e}=(Y_{e^{\prime}})_{e^{\prime}\in\binom{[n]}{2}\setminus e}$ for the set of observations excluded $e$, and $X_{e}=X_{i}X_{j}$ for $e=(i,j)$.

Fix $e\in\binom{[n]}{2}$. By linearity of differentiation, it is sufficient to prove the claim when only $p_{e}(\,\cdot\,|\,\cdot\,)$ depends on $\theta$.

Writing $H({\boldsymbol{X}},Y_{e}|{\boldsymbol{Y}}_{-e})$ by chain rule in two alternative ways we get

where in the last identity we used the conditional independence of $Y_{e}$ from ${\boldsymbol{X}}$, ${\boldsymbol{Y}}_{-e}$, given $X_{e}$. Differentiating with respect to $\theta$, and using the fact that $H({\boldsymbol{X}}|{\boldsymbol{Y}}_{-e})$ is independent of $p_{e}(\,\cdot\,|\,\cdot\,)$, we get

Consider the first term. Singling out the dependence of $H(Y_{e}|X_{e})$ on $p_{e}$ we get

We follow the same steps for the second term (171):

Taking the difference of Eq. (174) and Eq. (177) we obtain the desired formula. ∎

2 Application to the stochastic block model

We next apply the general differentiation Lemma 7.1 to the stochastic block model. As mentioned above, this fits the framework in the previous section, by setting ${\boldsymbol{Y}}$ be the adjacency matrix of the graph ${\boldsymbol{G}}$, and taking $p_{{\boldsymbol{X}}}$ to be the uniform distribution over $\{+1,-1\}^{n}$. For the sake of convenience, we will encode this as $Y_{e}=2G_{e}$. In other words ${\mathcal{Y}}=\{+1,-1\}$ and $Y_{e}=+1$ (respectively $=-1$) encodes the fact that edge $e$ is present (respectively, absent). We then have the following channel model for all $e\in\binom{[n]}{2}$:

We will be eventually interested in setting $\theta=\lambda_{n}$ to make contact with the setting of Theorem 1.4.

Let $I({\boldsymbol{X}};{\boldsymbol{G}})$ be the mutual information of the two-groups stochastic block models with parameters $p_{n}=p_{n}(\theta)$ and $q_{n}=q_{n}(\theta)$ given by Eq. (180). Then there exists a numerical constant $C$ such that the following happens.

For any $\theta_{\rm max}>0$ there exists $n_{0}(\theta_{\rm max})$ such that, if $n\geq n_{0}(\theta_{\rm max})$ then for all $\theta\in[0,\theta_{\rm max}]$,

We let $Y_{e}=2G_{2}-1$ and apply Lemma 7.1. Simple calculus yields

Notice that, letting $\Delta_{n}=\sqrt{\overline{p}_{n}(1-\overline{p}_{n})\theta/n}$,

Since have $|\Delta_{n}/\overline{p}_{n}|,|\Delta_{n}/(1-\overline{p}_{n})|\leq\sqrt{\theta/[\overline{p}_{n}(1-\overline{p}_{n})n]}\to 0$, and $\widehat{x}_{e}({\boldsymbol{Y}}_{-e})|\leq 1$, we obtain the following bounds by Taylor expansion

where $B_{0}\equiv\log(\overline{p}_{n}/(1-\overline{p}_{n}))$ and $C$ will denote a numerical constant that will change from line to line in the following. Such bounds hold for all $\theta\in[0,\theta_{\rm max}]$ provided $n\geq n_{0}(\theta_{\rm max})$.

Rewriting this identity in terms of $\widehat{x}_{e}({\boldsymbol{Y}})$, $\widehat{x}_{e}({\boldsymbol{Y}}_{-e})$, we obtain

Using the definition of $p_{e}(y_{e}|x_{e})$, we obtain

This in particular implies $|b(y_{e})|\leq\sqrt{\theta/[n\overline{p}_{n}(1-\overline{p}_{n})]}$. From Eq. (192) we therefore get (recalling $|\widehat{x}_{e}({\boldsymbol{Y}}_{-e})|\leq 1$)

Finally we rewrite the sum over $e\in\binom{[n]}{2}$ explicitly as sum over $i<j$ and recall that $X_{e}=X_{i}X_{j}$ to get

Since ${\boldsymbol{Y}}$ is equivalent to ${\boldsymbol{Y}}$ (up to a change of variables) and $I({\boldsymbol{X}};{\boldsymbol{G}})=H({\boldsymbol{X}})-H({\boldsymbol{G}}|{\boldsymbol{G}})$, with $H({\boldsymbol{X}})=n\log 2$ is independent of $\theta$, this is equivalent to our claim (recall the definition of ${\sf MMSE}_{n}(\,\cdot\,)$, Eq. (16)). ∎

3 Proof of Theorem 1.4

From Lemma 7.2 and Theorem 1.1, we obtain, for any $0<\lambda_{1}<\lambda_{2}$,

Acknowledgments

Y.D. and A.M. were partially supported by NSF grants CCF-1319979 and DMS-1106627 and the AFOSR grant FA9550-13-1-0036. Part of this work was done while the authors were visiting Simons Institute for the Theory of Computing, UC Berkeley.

Appendix A Estimation metrics: proofs

where the equality on the second line follows because $({\boldsymbol{X}},{\boldsymbol{G}})$ is distributed as $(-{\boldsymbol{X}},{\boldsymbol{G}})$. The last inequality yields the desired upper bound ${\sf vmmse}_{n}(\lambda)\leq{\sf MMSE}_{n}(\lambda)$.

In order to prove the lower bound on ${\sf vmmse}_{n}(\lambda)$ assume, for the sake of simplicity, that the infimum in the definition (32) is achieved at a certain estimator ${\boldsymbol{\widehat{x}}}(\,\cdot\,)$. If this is not the case, the argument below can be easily adapted by letting ${\boldsymbol{\widehat{x}}}(\,\cdot\,)$ be an estimator that achieves error within ${\varepsilon}$ of the infimum.

Under this assumption, we have, from (32),

where the last identity follows since the minimum over $\alpha$ is achieved at $\alpha=\langle{\boldsymbol{X}},{\boldsymbol{\widehat{x}}}({\boldsymbol{G}})\rangle/\|{\boldsymbol{\widehat{x}}}({\boldsymbol{G}})\|_{2}^{2}$.

Consider next the matrix minimum mean square error. Let ${\boldsymbol{\widehat{x}}}({\boldsymbol{G}})=(\widehat{x}({\boldsymbol{G}}))_{i\in[n]}$ an optimal estimator with respect to ${\sf vmmse}_{n}(\lambda)$, and define

Using Eq. (14) and the optimality of posterior mean, we obtain

The desired lower bound in Eq. (41) follows by comparing Eqs. (206) and (211).

A.2 Proof of Lemma 3.6

Notice that $\|{\boldsymbol{\xi}}({\boldsymbol{G}})\|_{2}=\sqrt{n}$. Also by the proof in previous section, see Eq. (206), we have

and therefore (since $|\langle{\boldsymbol{X}},{\boldsymbol{\xi}}({\boldsymbol{G}})\rangle|\leq n$)

Next consider the definition of overlap (33). Consider the randomized estimator ${\boldsymbol{\widehat{s}}}:\mathcal{G}_{n}\to\{+1,-1\}^{n}$ defined by letting ${\boldsymbol{\widehat{s}}}({\boldsymbol{G}})=(\widehat{x}_{i}({\boldsymbol{G}}))_{i\in[n]}$ with

independently across $i\in[n]$. (Formally, ${\boldsymbol{\widehat{s}}}:\mathcal{G}_{n}\times\Omega\to\{+1,-1\}^{n}$ with $\Omega$ a probability space, but we prefer to avoid unnecessary technicalities.)

with the $O(n^{-1/2})$ uniform in ${\boldsymbol{X}},{\boldsymbol{G}}$. This yields the desired lower bound since, by dominated convergence,

Appendix B Additional technical proofs

Setting $t=Cn^{2}\overline{p}_{n}$ for large enough $C$ yields the required result.

B.2 Proof of Lemma 6.1

Let us start from point $(a)$,. Since ${\sf mmse}(\gamma,{\varepsilon})={\varepsilon}+(1-{\varepsilon})(1-{\sf mmse}(\gamma))$, it is sufficient to prove this claim for

where the first and last equalities follow by symmetry.

Differentiating with respect to $\gamma$ (which can be justified by dominated convergence):

Now applying Stein’s lemma (or Gaussian integration by parts):

Using the trigonometric identity ${\text{sech}}(z)^{2}=1-\tanh(z)^{2}$, the shorthand $T=\tanh(\gamma+\sqrt{\gamma}Z)$ and identity (223) above:

Now, let $\psi(z)={\text{sech}}^{4}(z)$, whereby we have

Hence, to prove that $G^{\prime\prime}(\gamma)$ is concave on $\gamma\geq 0$, it suffices to show that $\partial H/\partial x$, $\partial H/\partial y$ are non-positive for $x,y\geq 0$. By properties $(ii)$ and $(iii)$ above we can differentiate $H$ with respect to $x,y$ and interchange differentiation and expectation.

We first prove that $\partial H/\partial x$ is non-positive:

Here $\varphi(z)$ is the Gaussian density $\varphi(z)=\exp(-z^{2}/2)/\sqrt{2\pi}$. Since $z\psi^{\prime}(z)\leq 0$ by property $(i)$ and $\varphi(z-y)>0$ we have the required claim.

Computing the derivative with respect to $y$ yields

where the last line follows from the fact that $\psi^{\prime}(u)$ is odd and $\varphi(u)$ is even in $u$. Consequently

Since $\varphi(y-z)\geq\varphi(y+z)$ and $\psi^{\prime}(xz)\leq 0$ for $y,z\geq 0$, the integrand is negative and we obtain the desired result.

B.3 Proof of Remark 6.5

For any random variable ${\boldsymbol{R}}$ we have

Since $H({\boldsymbol{X}}|{\boldsymbol{X}}{\boldsymbol{X}}^{{\sf T}},{\boldsymbol{R}})\leq H({\boldsymbol{X}}|{\boldsymbol{X}}{\boldsymbol{X}}^{{\sf T}})\leq\log 2$ (given ${\boldsymbol{X}}{\boldsymbol{X}}^{{\sf T}}$ there are exactly $2$ possible choices for ${\boldsymbol{X}}$), this implies

The claim (147) follows by applying the last inequality once to ${\boldsymbol{R}}=\emptyset$ and once to ${\boldsymbol{R}}=({\boldsymbol{X}}({\varepsilon}),{\boldsymbol{Y}}(\lambda))$ and taking the difference.

The claim (148) follows from the fact that ${\boldsymbol{Y}}(0)$ is independent of ${\boldsymbol{X}}$, and hence $I({\boldsymbol{X}};{\boldsymbol{X}}({\varepsilon}),{\boldsymbol{Y}}(0))=I({\boldsymbol{X}};{\boldsymbol{X}}({\varepsilon}))=n{\varepsilon}\log 2$.

For the second claim, we prove that $\limsup_{n\to\infty}H({\boldsymbol{X}}|{\boldsymbol{Y}}(\lambda),{\boldsymbol{X}}({\varepsilon}))\leq\delta(\lambda)$ where $\delta(\lambda)\to 0$ as $\lambda\to\infty$, whence the claim follows since $H({\boldsymbol{X}})=n\log 2$. We claim that we can construct an estimator ${\boldsymbol{\widehat{x}}}({\boldsymbol{Y}})\in\{-1,1\}^{n}$ and a function $\delta_{1}(\lambda)$ with $\lim_{\lambda\to\infty}\delta_{1}(\lambda)=0$, such that, defining

To prove this claim, it is sufficient to consider ${\boldsymbol{\widehat{x}}}({\boldsymbol{Y}})={\operatorname{\rm{sgn}}}({\boldsymbol{v}}_{1}({\boldsymbol{Y}}))$ where ${\boldsymbol{v}}_{1}({\boldsymbol{Y}})$ is the principal eigenvector of ${\boldsymbol{Y}}$. Then [CDMF09, BGN11] implies that, for $\lambda\geq 1$, almost surely,

Hence the above claim holds, for instance, with $\delta_{1}(\lambda)=2/\lambda$.

Then expanding $H({\boldsymbol{X}},E|{\boldsymbol{Y}}(\lambda),{\boldsymbol{X}}({\varepsilon}))$ with the chain rule (whereby $E=E(\lambda,n)$), we get:

Since $E$ is a function of ${\boldsymbol{X}},{\boldsymbol{Y}}(\lambda)$, $H(E|{\boldsymbol{X}},{\boldsymbol{Y}}(\lambda))=0$. Furthermore $H(E|{\boldsymbol{Y}}(\lambda),{\boldsymbol{X}}({\varepsilon}))\leq\log 2$ since $E$ is binary. Hence: