The Mutual Information in Random Linear
Estimation Beyond i.i.d. Matrices
Jean Barbier†,∗ and Nicolas Macris†

Antoine Maillard and Florent Krzakala

arXiv:1802.08963v1 [] 25 Feb 2018

† Communication Theory Laboratory, EPFL, Switzerland.
LPS ENS, CNRS, PSL, UPMC & Sorbonne Université,
∗ Probability and Applications Group, QMUL, United-Kingdom.
Paris, France.

Abstract—There has been definite progress recently in proving
the variational single-letter formula given by the heuristic replica
method for various estimation problems. In particular, the replica
formula for the mutual information in the case of noisy linear estimation with random i.i.d. matrices, a problem with applications
ranging from compressed sensing to statistics, has been proven
rigorously. In this contribution we go beyond the restrictive i.i.d.
matrix assumption and discuss the formula proposed by Takeda,
Uda, Kabashima and later by Tulino, Verdu, Caire and Shamai
who used the replica method. Using the recently introduced
adaptive interpolation method and random matrix theory, we
prove this formula for a relevant large sub-class of rotationally
invariant matrices.

I. I NTRODUCTION
Few problems are as ubiquitous in computer science as the
one of random linear estimation, that plays a fundamental
role in machine learning [1], statistics [2] and communication
[3]. Computing the information theoretic limitation for the
estimation of a signal given the knowledge of its random
linear projections has many applications, e.g., compressed
sensing [2], code division multiple access (CDMA) [4] or error
correcting codes [5, 6]. The problem is defined as follows:
Consider a signal vector X ∈ Rn with i.i.d. entries distributed
according to a “prior” P0 over R with bounded support (an
hypothesis that can be relaxed). One is given m measurements
r
λ
Yµ =
(ΦX)µ + Zµ , µ = 1, . . . , m ,
(1)
n
in which λ > 0 is the signal to noise ratio (snr), Z =
i.i.d.
m×n
(Zµ )m
is the
µ=1 ∼ N (0, 1) is a Gaussian noise and Φ ∈ R
measurement matrix. We will consider the “high-dimensional
limit”, namely m, n → ∞ such that α ≡ m/n stays finite.
There has been a considerable amount of work on this
model in the case where Φ is a random matrix whose elements
are i.i.d. standard Gaussian. In particular a pionnering work
by Tanaka [4] using a statistical physics calculation and the
replica method [7] proposed a single-letter formula for the
normalized mutual information between the measurements and
the signal in ≡ n1 I(X; Y|Φ). The so-called Tanaka formula,
orginally written for the CDMA problem (where each element
of X is taken i.i.d. from ±1), has been generalized and applied
to many problems (e.g. in [8, 9]). After nearly 15 years, it has
been proven with different approaches [10–13], a spectacular
confirmation of the replica calculation.

In this paper, we endeavour to go beyond the very restrictive
simple i.i.d. measurement matrix assumption and consider
instead a more complex situation where Φ is now taken from
a non-trivial, and correlated, random ensemble. This is both
more relevant to practical cases, and more realistic in terms
of modeling real statistical situations.
II. R ESULT AND RELATED WORKS
The random linear estimation problem with correlated, non
i.i.d. matrices has been considered, again with the replica
method, and a solution was proposed by Takeda, Uda and
Kabashima in the case of CDMA [14] for matrices taken
from a rotationally invariant ensemble. The replica formula
was later extended by Tulino, Caire, Verdu and Shamai [9] for
such similar ensembles in order to allow for more complicated
priors such as Gauss-Bernoulli ones. These works point to a
generic conjecture, that we now describe, giving the singleletter formula for the mutual information.
Consider a measurement matrix Φ = OΣN| where O
and N are both orthogonal matrices and Σ is diagonal (nonsquare if α 6= 1). The matrices Σ, N, O are independent and
N is distributed uniformly, according to the Haar measure
of its orthogonal group, in which case Φ is said to be
right-rotationally invariant (if O is also Haar distributed the
ensemble is simply called rotationally invariant). The matrix
R ≡ n1 Φ| Φ = n1 NΣ| ΣN| plays an important role. For
general rotationally invariant ensembles its eigenvalues are not
necesssarily i.i.d. but typically are such that n1 Σ| Σ has a
suitable limiting eigenvalue distribution (as in fact assumed
in [14]). The limit of the normalized mutual information is
conjectured to be
lim in = sup iRS (E, r; λ)

n→∞

(2)

(E,r)∈Γ

where the so-called replica symmetric potential iRS (E, r; λ) =
iRS is defined as
R Eλ
√
(3)
iRS ≡ I(X; rX + Z) + 21 0 RR (−z)dz − rE
2 .
Here we have used the R-transform of the matrix
√ R (see [3]
for an introduction to such transforms). I(X; rX + Z), that
we simply denote I(r) later on, is the
√ mutual information for
the scalar Gaussian channel Y = rX + Z, X ∼ P0 and

Z ∼ N (0, 1). Moreover, Γ is the set of critical points of the
potential, or state evolution fixed points (ρ ≡ EP0 [X 2 ])

√
Γ ≡ (E, r) ∈ [0, ρ] × R+ E = mmse(X| r X + Z),
r = λRR (−Eλ) .
A virtue of the formula (3) is that the details of the rotation
invariant matrix ensemble only enter through the R-transform.
Note the slight difference with the potential written in [9]:
In the potential (3) a factor 1/2, not present in [9], multiplies
both the integrated R-transform and −rE. This is because
they consider the complex Φ case while we consider the real
case (nevertheless, we believe that our proof techniques could
easily be generalized to include the complex case).
Interestingly, Manoel et al [15] and Reeves [16] were able to
formally re-derive equivalent results independently for a subclass of rotationally invariant matrices by considering multilayered estimation problems. This line of work combined with
our present rigorous work is giving a lot of credibility to the
replica conjecture for the general rotation invariant ensemble.
A. Main result
Our main result is a proof of the replica conjecture (2) for
a specific, but large, set of correlated matrices. We hope it
paves the way towards a completely general proof, as the
non-rigourous replica calculation only assumes right-rotational
invariance of Φ. We assume that the m × n matrix Φ can be
decomposed as follows:
Φ = Φ0 W

(4)

in which all elements of the m × n matrix W are i.i.d.
Gaussians N (0, 1/n) with mean zero and variance 1/n, Φ0
is a m × m random matrix, and W, Φ0 are independent.
Concerning Φ0 , our analysis is currently complete under
the assumption that it is a product of a finite number of
independent matrices, each with i.i.d. matrix-elements that are
either bounded or standard Gaussians. The case of a product
of i.i.d. standard Gaussian matrices constitutes an interesting
example that has been considered in [15].
Our goal here is to give a rigorous proof of (2) in the
setting of matrices (4) with the independence assumptions for
Φ0 . Some of our technical calculations are based on previous
related works, and all of them will be discussed in a complete
manner in a longer contribution.
Theorem 2.1 (Replica formula): Assume that the prior P0
has compact support or, in other words, the signal is bounded.
Then with n, m, Φ, R, iRS defined as before (in particular Φ
satisfies (4) and the subsequent hypothesis), one has
lim in = inf sup iRS (E, r; λ) .

n→∞

r≥0 E∈[0,ρ]

Remark 2.1 (Equivalent expressions of the replica formula):
The right hand side in the theorem above can also be written as
sup(E,r)∈Γ iRS (E, r; λ) (if the extremizers are not attained at
the boundaries, which is the case when noise is present) or as
inf E∈[0,ρ] supr≥0 iRS (E, r; λ). A proof of such equivalences,
in the case of generalized estimation, is found in [13].

Remark 2.2 (Right-rotation invariance of the ensemble):
Note that (4) implies the right-rotation invariance of Φ because
of the rotation invariance of W. Our result thus covers a subclass of right-rotationally invariant matrices.
Remark 2.3 (Relaxing the assumptions on Φ0 ): The assumptions on Φ0 come from the fact that a complete rigorous
analysis requires proving the concentration of the “free energy” of an interpolating model (see below; the free energy
is equal to the mutual information up to a trivial additive
constant). This involves the use of tools such as the McDiarmid
bounded difference inequality and/or the Gaussian Poincaré
inequality, which require some independence between degrees
of freedom. If one assumes concentration of the free energy of
the interpolating model then one can relax these assumptions
to the following more general ones. It then suffices to assume
that n1 Φ0| Φ0 has a well-defined, positively and compactly supported, asymptotic eigenvalue distribution in the limit n → ∞.
We also remark that concentration proofs of the free energy
of the original and interpolated models are technically similar,
however we have not established a purely logical implication
between the two. If such an implication holds one could also
replace the independence assumption on Φ0 by an assumption
of concentration of the free energy.
Remark 2.4 (Relaxing the assumption on P0 ): Boundedness
of the signal is again used to obtain concentration results for
the free energy but it can presumably be removed using a
limiting argument as in [17].
B. Related works
There has been a lot of effort recently [10–13] to prove the
Tanaka formula for random i.i.d. matrices. Our strategy in the
present paper is to follow the adaptive interpolation method
introduced in [18, 19]. This method, in particular, has been
used by the authors of [13] to reach a rigorous demonstration
of the replica formula for the mutual information for the case
of i.i.d. measurement matrix Φ, in the more general situation of “generalized linear estimation” i.e., with an arbitrary
measurement channel (instead of just a random additive noise
as in (1)). Some steps of our current approach consequently
follow similar ones in [13] (but with key differences) and we
will refer to this work when necessary. We believe, in fact,
that the approach presented in the present paper could further
be generalized as well to generalized linear estimation with
rotationally invariant matrices to reach the formula conjectured
by Kabashima in [20]. This is left for future work.
Perhaps the most important consequence of the replica
formula is that it predicts the value of the minimum meansquare error (MMSE) in the reconstruction of the signal X. In
fact, it is conjectured (and proved for Gaussian matrices [11,
12]) to be given by the value E that extremizes (3). While
we consider here mainly the information theoretic result, a
large body of work has focused on algorithmic approaches to
random linear estimation, and investigated whether the MMSE
is efficiently (say, in polynomial time) achievable.
For Gaussian matrices, the most successful approach, so far,
again originated in statistical physics [21, 22] and is called

approximate message-passing (AMP) [23]. AMP is Bayesoptimal and efficiently achieves the MMSE for a large set of
parameters, as proven in [11]. There, however, might exist a
region called “hard” where this is not the case, and polynomial
algorithms improving on AMP are not known. Whether there
exists an efficient algorithm that is able to beat AMP in the
hard region is widely considered to be a notoriously difficult
problem (see e.g. [24] and reference therein).
For rotationally invariant matrices, different but related
approaches were proposed [14, 25]. In particular, the general
expectation-propagation (EP) [26] leads to a powerful scheme
in this context [27]. Recently, Rangan, Schniter and Fletcher
proposed a variation of EP called VAMP [28] and showed that
it follows the fixed point equation (called state evolution) of
the potential (3). Interestingly, the multi-layer AMP algorithm
of Manoel et al. [15] also has the same fixed point. Our result
thus supports that VAMP (and multi-layer AMP) are Bayesoptimal and efficiently reach the MMSE in the “easy” region
of random linear estimation with these correlated matrices, just
as AMP in the case of i.i.d. Gaussian matrices.
III. P ROOF BY THE ADAPTIVE INTERPOLATION METHOD
We give here the main steps of the proof of Theorem 2.1. We
will use the adaptive interpolation method, introduced in [18],
and then applied in [19] and [13]. It is a powerful evolution of
the interpolation method developed by Guerra and Toninelli in
the context of spin glasses [29]. Many steps of the proof follow
the ones of [13], and we will refer to them when necessary.
A. Interpolating estimation problem
Let E : [0, 1] → R+ be a continuous “interpolation
Rt
e
function”, r ≥ 0 and t ∈ [0, 1]. Define E(t)
≡ 0 E(s)ds
e 0 (t) = E(t)), that plays the role of a signal-to-noise
(and thus E
ratio. Assume one has access to the following two t-dependent
observation channels for i = 1, . . . , n and µ = 1, . . . , m:
(
Yt,µ
Yet,i

=
=

q
√

λ(1−t)
(ΦX)µ
n

+

q

λ e
0
n E(t)(Φ V)µ

+ Zµ ,

(5)

rtXi + Zei .

It is a simple exercise (see e.g. [11]) to show that the
e t |Φ)
normalized mutual information in (t) ≡ n1 I(X, V; Yt , Y
for the interpolation estimation problem is related to the
posterior normalization (or partition function) through
R
e
in (t) = − n1 E ln dP0 (x)Dve−H(t,x,v;Yt ,Yt ,Φ) − α+1
2 . (7)
This interpolating mutual information verifies
(
in (0) = in ,
0
e
in (1) = I(r) + α2 EX 0 ln(1 + E(1)X
),

where X 0 ∼ p0n , with p0n the empirical spectral distribution of
the m×m matrix n1 Φ0| Φ0 . The second term in the expression
of in (1) (sometimes refered to as a Shannon transform, see
e.g. [3]) is obtained using the celebrated “log-det formula”
for the mutual information n1 I(Y1 ; V|Φ0 ) of an i.i.d. Gaussian
input multiplied by the matrix Φ0 and under additive Gaussian
noise, see e.g. [3].
Now a crucial step in our proof, that is a consequence of
the particular form of the measurement matrix (4), is that as
n grows, the second term in in (1) can be replaced by an
integrated R-transform:
R E(1)
e
RR (−u)du + On (1) ,
(9)
in (1) = I(r) + 12 0
where RR (z) is the R-transform associated with the asymptotic spectrum of R = n1 Φ| Φ. We give the definition of this
transform as well as the proof of (9) in the next section.
Remark 3.1 (A word about notations): We define the Gibbs
Bracket h−it as the expectation w.r.t. the posterior (6). In constrast, we denote by E the joint expectation w.r.t. all quenched
variables (i.e. fixed by the realization of the problem), namely
e t , or equivalently w.r.t. Φ0 , W, X, V, Z and Z.
e
Yt and Y
B. Useful tools from random matrix theory
In this paragraph we show how to deduce (9) from (8). Note
R E(1)
e
X0
0
e
EX 0 ln(1 + E(1)X
) = EX 0 0
du 1+uX
0 .
The result thus follows if the following relation is true :
0

In the following we assume λ = 1, as it amounts to a scaling of
i.i.d.
Φ. Here (Zei ), (Zµ ), (Vµ ) i.i.d.
∼ N (0, 1) whereas (Xi ) ∼ P0 . The
n
inference problem is to recover both X = (Xi )i=1 and V =
e
(Vµ )m
µ=1 from the knowledge of the observations Yt , Yt and
0
the matrix Φ (and thus of Φ and W too as the decomposition
(4) is assumed to be known).
In the Bayesian setting the posterior associated with this
inference problem, written in the Gibbs-Boltzmann form, is
−H(t,x,v;Yt ,Yt ,Φ)
e t , Φ) = RdP0 (x)Dve
dP (x, v|Yt , Y
, (6)
dP0 (x)Dve−H(t,x,v;Yt ,Yet ,Φ)
Qm
2
where Dv ≡ µ=1 dvµ (2π)−1/2 e−vµ /2 is the standard Gaussian measure, and we have defined the interpolating Hamiltoe t , Φ) as
nian H = H(t, x, v; Yt , Y
q
q
√
e
E(t)
1
1−t
1 e
0
2
H ≡ 2 kYt −
rt xk22 ,
n Φx−
n Φ vk2 + 2 kYt −
e

(8)

X
RR (−u) = αEX 0 [ 1+uX
0 ] + O n (1) .

(10)

This is a well known relation in random matrix theory. For
matrices of the form R = W| TW, where W is a Gaussian
m×n matrix with i.i.d. N (0, 1/n) elements, and T = n1 Φ0| Φ0
a non negative m × m matrix with a limiting spectral distribution, this was already shown by Marcenko and Pastur
in 1967 [30] in the language of the Stieltjes transform. See
also [31] for generalizations. Denoting by gR (z) and gT (z) (z
a complex number outside the specrum of the matrices) the
limiting Stieltjes transforms of the matrices R and T, we have
[30, 31] that the Marcenko-Pastur formula takes the form
z(gR (z))2 + αgT (−1/gR (z)) + (1 − α)gR (z) = 0 .
Simple algebra then implies (gR−1 is the inverse function)
gR−1 (z) + z −1 = −αz −2 (gT (−z −1 ) − z) .

−1
−1
Since
and gT (z) ≡
R dτ (x)by definition RR (z) ≡ gR (−z) − z
,
dτ
being
the
limiting
eigenvalue
distribution
of T, this
x−z
R
x
relation is nothing else than RR (−z) = α dτ (x) 1+zx which
is equivalent to (10) when n → ∞. We refer to the review [32]
for a more modern discussion using free probability concepts.

C. Mutual information variation
In order to “compare” the potential (3) with the mutual
information,
we use the trivial identity in = in (0) = in (1) −
R1 0
i
(t)dt
which
becomes, using (9),
n
0
R
R1
e
E(1)
RR (−u)du − 0 i0n (t)dt + On (1) . (11)
in = I(r) + 12 0
Pn
We now evaluate i0n (t). Define Q ≡ n1 i=1 Xi xi , called
the overlap, and the vector ut = (ut,µ )m
µ=1 with
q
q
e
E(t)
0
ut,µ ≡ 1−t
n (Φ(X−x))µ +
n (Φ (V − v))µ +Zµ .
Lemma 3.1 (Mutual information variation): For t ∈ (0, 1)
r
i0n (t) = (ρ − EhQit ) + On (1)
2
1
+ 2 E Z| (Φ0 Φ0| )ut [E(t) − (ρ − Q)] t (12)
2n
in which limn→∞ On (1) = 0 uniformly in t ∈ (0, 1).
The proof of this lemma, see [33], is very similar to the one
of Proposition 4 of [13]. The idea is to write explicitly the
derivative i0n (t) and then to integrate by parts the quenched
Gaussian variables V and W, before using the Nishimori
identity. This identity is a consequence of Bayes rule and the
fact that we consider the optimal Bayesian setting, namely that
all hyperparameters in the problem such as the snr and P0 are
known and used when defining the posterior, see [13, 18, 24].
D. Overlap concentration
The next lemma essentially states that the overlap concentrates around its mean, and plays a key role in our proof. The
proof technique for Bayesian inference has been developped
in [11, 34–36] and is akin to the analysis reviewed for example
in [37]. The point however here is that in Bayesian inference
overlap concentration can be proved in the whole phase
diagram. We will refer to [13, 18] where the analysis has been
made quite generic.
We introduce a “small” perturbation of the interpolating
estimation problemP
by adding to the interpolating
√ b Hamilton
2
nian H the term
xi Zi ) where
i=1 (xi /2 − xi Xi −
(Zbi )ni=1 i.i.d.
∼ N (0, 1). This term can be interpreted as coming
from a√set of extra observations from a Gaussian side-channel
bi for i = 1, . . . , n. Importantly this term preYbi = Xi + Z
serves the Nishimori identity. The new Hamiltonian defines a
new Gibbs bracket h−it, and interpolating mutual information
in, (t). All the calculations of the previous section trivially
extend. This perturbation induces only a small change in the
mutual information, namely of the order of :
Lemma 3.2 (Mutual information variation under perturbation): Let P0 with bounded support. For all  > 0 and all
t ∈ [0, 1], |in, (t) − in (t)| = O() where O() depends only
on the size of the support of P0 , and on α.

Proof: A computation using Gaussian integration by parts
∂f (t)
| = 12 |EhQit, |.
and the Nishimori identity gives | n,
∂
This small perturbation forces the overlap to concentrate:
LemmaR 3.3 R(Overlap concentration): For any 0 < a < b < 1,
b
1
limn→∞ a d 0 dt Eh(Q − EhQit, )2 it, = 0.
We refer to [13, 18] for a detailed proof. As long as the concentration of the free energy of the interpolating model holds
and that the unperturbed Hamiltonian satisfies the Nishimori
identity (i.e., comes from a Bayesian inference probem) the
analysis in [13, 18] applies verbatim. In other words the details
of the unperturbed Hamiltonian do not matter. We stress that
this lemma is the only place where the concentration of the free
energy of the interpolating model is needed. For the present
model under the assumptions on Φ0 this follows from Gaussian
Poincaré and McDiarmid inequalities much as in [13].
Note that the existence of the limit of the integrand in
Lemma 3.3 as n → ∞ is not known (and seems difficult
to prove). Hence one cannot use Lebesgue’s dominated convergence theorem to exchange the limit and the -integral.
However, an elementary analysis argument based on the mean
value theorem shows the existence of a sequence (n )n≥1 that
converges to 0 such that
R1
limn→∞ 0 dt Eh(Q − EhQit,n )2 t,n = 0 .
(13)
Note that Lemma 3.2 gives that in,n (t) and in (t) have same
limit provided it exists. In the next sections, in order to
alleviate the notations in this short manuscript, we abusively
remove the perturbation subscript n since it makes no essential difference for the subsequent proofs but it is understood
that all quantities are computed for the n -perturbed model.
E. Upper and lower bounds
This part is similar to parts 5.3 and 5.4 of [13], or to what
is done in [19]. As suggested by (12), in order to recover
the potential on the r.h.s. of (11), we want to choose for the
interpolating function
e 0 (t) = ρ − EhQit .
E(t) = E

(14)

Note that (14) is actually a first-order differential equation
e
e
in E(t)
(EhQit is a function of E(t)).
Because EhQit is
1
e
a bounded C function of (E(t), r), the parametric CauchyLipschitz theorem gives the following existence lemma.
Lemma 3.4 (Optimal interpolation function): Let n ∈ N∗ .
For all r ≥ 0, the differential equation (14) admits a unique
(r)
En (t) ∈ [0, ρ]. Moreover the mapping r ∈ R+ 7→
Rsolution
1 (r)
En (s)ds ∈ [0, ρ] is continuous.
0
(r)
We choose this optimal solution En (t). We then apply
the concentration (13) for replacing the overlap by its mean
EhQit in (12) under the integral in (11). We use the CauchySchwartz inequality to show
to an On (1)
R 1that this is possibleRup
1 (r)
correction. This leads to 0 i0n (t)dt = (r/2) 0 En (t)dt +
O n (1) . Therefore (11) and (12) allow to deduce the following.
Lemma 3.5 (Fundamental identity): Let (rn )n∈N ∈ RN
+ be
a bounded sequence. Then
R 1 (r )
in = iRS ( 0 En n (s)ds, rn ) + On (1) .
(15)

It immediately implies an upper bound:
Proposition 3.1 (Upper bound): The mutual info. verifies
lim sup in ≤ inf sup iRS (E, r) .
n→∞

r≥0 E∈[0,ρ]

(16)

Proof: Choose a constant sequence rn = r. Lemma 3.5
then implies lim supn→∞ in ≤ supE∈[0,ρ] iRS (E, r). This is
true for any r ≥ 0, therefore the result.
The lower bound is a bit more involved. Details of similar
computations can be found in [13, 19]
Proposition 3.2 (Lower bound): The mutual info. verifies
lim inf in ≥ inf sup iRS (E, r) .
n→∞

r≥0 E∈[0,ρ]

(17)

Proof: Note that due to our hypothesis and its consequence (10), the function h : z 7→ RR (−z) is a C 1 function
defined for all z ≥ 0, and verifies i) h(0) = RR (0) is finite;
ii) h0 (z) < 0 for all z > 0; and iii) h(z) > 0 for all z > 0.
K ≡ max (ρ, h(0)). Then the mapping r ∈ [0, K] 7→
RDefine
1 (r)
h( 0 En (t)dt) ∈ [0, K] is continuous by composition. It
must thus admit a fixed point rn∗ . It thus only remains to show
R 1 (r∗ )
iRS ( 0 En n (t)dt, rn∗ ) = supE∈[0,ρ] iRS (E, rn∗ ) .
(18)
This is true because at fixed r, the function gr (E) ≡ iRS (E, r)
is strictly concave since gr00 (E) = h0 (E)/2 < 0. The conclusion follows from the fact that the derivative
only vanish
R 1 can
(r ∗ )
at the (achieved) maximum, and that gr0 n∗ ( 0 En n (t)dt) = 0;
R 1 (r∗ )
indeed this is the fixed point equation rn∗ = h( 0 En n (t)dt).
Finally (15) yields in = supE∈[0,ρ] iRS (E, rn∗ ) + On (1) ≥
inf r≥0 supE∈[0,ρ] iRS (E, r) + On (1), and thus the result.
ACKNOWLEDGMENT
We acknowledge funding from the ERC under the European
Union’s FP7 Grant Agreement 307087-SPARCS, the SNSF
grant 200021-156672, and the ANR PAIL. We also thank
Olivier Levêque and Sundeep Rangan for helpful discussions.
R EFERENCES
[1] W. B. Johnson and J. Lindenstrauss, “Extensions of lipschitz mappings
into a hilbert space,” Contemporary mathematics, 1984.
[2] E. J. Candes and T. Tao, “Near-optimal signal recovery from random
projections: Universal encoding strategies?” IEEE Transactions on Information Theory, vol. 52, no. 12, pp. 5406–5425, Dec 2006.
[3] A. M. Tulino and S. Verdú, Random matrix theory and wireless
communications. Now Publishers Inc, 2004, vol. 1.
[4] T. Tanaka, “A statistical-mechanics approach to large-system analysis of
cdma multiuser detectors,” IEEE Transactions on Information Theory,
vol. 48, no. 11, pp. 2888–2910, Nov 2002.
[5] A. R. Barron and A. Joseph, “Toward fast reliable communication at
rates near capacity with gaussian noise,” in 2010 IEEE International
Symposium on Information Theory, June 2010, pp. 315–319.
[6] J. Barbier and F. Krzakala, “Approximate message-passing decoder and
capacity achieving sparse superposition codes,” IEEE Transactions on
Information Theory, vol. 63, no. 8, pp. 4894–4927, Aug 2017.
[7] M. Mézard, G. Parisi, and M.-A. Virasoro, Spin glass theory and beyond.
World Scientific Publishing Co., Inc., Pergamon Press, 1987.
[8] F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborová,
“Statistical-physics-based reconstruction in compressed sensing,” Phys.
Rev. X, vol. 2, p. 021005(18), May 2012.
[9] A. M. Tulino, G. Caire, S. Verdú, and S. Shamai, “Support recovery
with sparsely sampled free random matrices,” IEEE Transactions on
Information Theory, vol. 59, no. 7, pp. 4243–4271, July 2013.

[10] J. Barbier, M. Dia, N. Macris, and F. Krzakala, “The mutual information
in random linear estimation,” in 2016 54th Annual Allerton Conference
on Communication, Control, and Computing, 2016.
[11] J. Barbier, N. Macris, M. Dia, and F. Krzakala, “Mutual information and
optimality of approximate message-passing in random linear estimation,”
arXiv:1701.05823, 2017.
[12] G. Reeves and H. D. Pfister, “The replica-symmetric prediction for compressed sensing with gaussian matrices is exact,” vol. arxiv:1607.02524.
[13] J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová,
“Phase transitions, optimal errors and optimality of message-passing in
generalized linear models,” arXiv:1708.03395.
[14] K. Takeda, S. Uda, and Y. Kabashima, “Analysis of cdma systems that
are characterized by eigenvalue spectrum,” EPL (Europhysics Letters),
vol. 76, no. 6, p. 1193, 2006.
[15] A. Manoel, F. Krzakala, M. Mézard, and L. Zdeborová, “Multi-layer
generalized linear estimation,” in 2017 IEEE International Symposium
on Information Theory (ISIT), 2017, pp. 2098–2102.
[16] G. Reeves, “Additivity of information in multilayer networks via additive
gaussian noise transforms,” vol. abs/1710.04580, 2017.
[17] M. Lelarge and L. Miolane, “Fundamental limits of symmetric low-rank
matrix estimation,” ArXiv e-prints, Nov. 2016.
[18] J. Barbier and N. Macris, “The stochastic interpolation method: A
simple scheme to prove replica formulas in bayesian inference,”
arxiv:1705.02780.
[19] J. Barbier, N. Macris, and L. Miolane, “The Layered Structure of
Tensor Estimation and its Mutual Information,” in 47th Annual Allerton
Conference on Communication, Control, and Computing, 2017.
[20] Y. Kabashima, “Inference from correlated patterns: a unified theory for
perceptron learning and linear vector channels,” Journal of Physics:
Conference Series, vol. 95, no. 1, p. 012001, 2008.
[21] D. J. Thouless, P. W. Anderson, and R. G. Palmer, “Solution of‘solvable
model of a spin glass’,” Philosophical Magazine, vol. 35, no. 3, p.
593601, 1977.
[22] M. Mézard, “The space of interactions in neural networks: Gardner’s
computation with the cavity method,” Journal of Physics A: Mathematical and General, vol. 22, no. 12, pp. 2181–2190, 1989.
[23] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” Proceedings of the National Academy
of Sciences, vol. 106, no. 45, pp. 18 914–18 919, Nov 2009.
[24] L. Zdeborová and F. Krzakala, “Statistical physics of inference: thresholds and algorithms,” Advances in Physics, vol. 65, no. 5, p. 453, 2016.
[25] B. Çakmak, O. Winther, and B. H. Fleury, “S-AMP: approximate
message passing for general matrix ensembles,” vol. arxiv:1405.2767.
[26] T. P. Minka, “Expectation propagation for approximate bayesian inference,” in Proceedings of the Seventeenth Conference on Uncertainty in
Artificial Intelligence, ser. UAI’01, 2001, pp. 362–369.
[27] M. Opper and O. Winther, “Expectation consistent approximate inference,” Journal of Machine Learning Research, vol. 6, p. 21772204, 2005.
[28] S. Rangan, P. Schniter, and A. K. Fletcher, “Vector approximate message
passing,” vol. arxiv:1610.03082.
[29] F. Guerra and F. L. Toninelli, “The thermodynamic limit in mean field
spin glass models,” Communications in Mathematical Physics, vol. 230,
no. 1, pp. 71–79, 2002.
[30] V. A. Marčenko and L. A. Pastur, “Distribution of eigenvalues for some
sets of random matrices,” Mathematics of the USSR-Sbornik, vol. 1,
no. 4, p. 457, 1967.
[31] J. W. Silverstein, “Strong convergence of the empirical distribution of
eigenvalues of large dimensional random matrices,” Journal of Multivariate Analysis, vol. 55, no. 2, pp. 331–339, 1995.
[32] R. Speicher, “Free probability theory,” arXiv preprint arXiv:0911.0087,
2009.
[33] J. Barbier, N. Macris, A. Maillard, and F. Krzakala. [Online]. Available:
http://ipgold.epfl.ch/∼macris/main-publications/main rev.pdf
[34] N. Macris, “Griffith-Kelly-Sherman correlation inequalities: A useful
tool in the theory of error correcting codes,” IEEE Transactions on
Information Theory, vol. 53, no. 2, pp. 664–683, Feb 2007.
[35] S. B. Korada and N. Macris, “Tight bounds on the capacity of binary
input random cdma systems,” IEEE Transactions on Information Theory,
vol. 56, no. 11, pp. 5590–5613, Nov 2010.
[36] ——, “Exact solution of the gauge symmetric p-spin glass model on
a complete graph,” Journal of Statistical Physics, vol. 136, no. 2, pp.
205–230, 2009.
[37] M. Talagrand, Mean field models for spin glasses: Volume I: Basic
examples. Springer Science & Business Media, 2010, vol. 54.

