Information-theoretic bounds and phase transitions in clustering,
sparse PCA, and submatrix localization

arXiv:1607.05222v2 [math.ST] 23 Jan 2017

Jess Banks

Cristopher Moore
Roman Vershynin
Jiaming Xu ∗

Nicolas Verzelen

January 24, 2017

Abstract
We study the problem of detecting a structured, low-rank signal matrix corrupted with additive
Gaussian noise. This includes clustering in a Gaussian mixture model, sparse PCA, and submatrix
localization. Each of these problems is conjectured to exhibit a sharp information-theoretic threshold,
below which the signal is too weak for any algorithm to detect. We derive upper and lower bounds
on these thresholds by applying the first and second moment methods to the likelihood ratio between
these “planted models” and null models where the signal matrix is zero. For sparse PCA and submatrix
localization, we determine this threshold exactly in the limit where the number of blocks is√large or the
signal matrix is very sparse; for the clustering problem, our bounds differ by a factor of 2 when the
number of clusters is large. Moreover, our upper bounds show that for each of these problems there
is a significant regime where reliable detection is information-theoretically possible but where known
algorithms such as PCA fail completely, since the spectrum of the observed matrix is uninformative.
This regime is analogous to the conjectured ‘hard but detectable’ regime for community detection in
sparse graphs.
Keywords: First and second moment methods, clustering, information-theoretic bounds, sparse PCA, submatrix
localization

1

Introduction

Many problems in machine learning, signal processing, and statistical inference have a common, unifying
goal: reconstruct a low-rank signal matrix observed through a noisy channel. This framework can encompass
a wide range of tasks as we vary the channel and low-rank signal, but we focus here on the case where the
noise is additive and Gaussian, and the signal is relatively weak in comparison to the noise. To be precise,
suppose we are given an m × n data matrix
X =M +W

snr
with M = √ U V † ,
n

(1)

where snr is a fixed parameter characterizing the signal-to-noise ratio, U ∈ Rm×k and V ∈ Rn×k are generated
from some known prior distribution independent of n, and W ∈ Rm×n is a noise matrix whose entries are
independent Gaussians with unit variance. We will refer to this as the planted model : it consists of a noisy
∗ J.
Banks is with the Department of Mathematics, University of California, Berkeley, Berkeley, CA,
jess.m.banks@berkeley.edu. C. Moore is with the Santa Fe Institute, Santa Fe, NM, moore@santafe.edu. R. Vershynin is with the Department of Mathematics, University of Michigan, Ann Arbor, MI, romanv@umich.edu. N. Verzelen
is with UMR 729 MISTEA, INRA, Montpellier. J. Xu is with the Krannert School of Management, Purdue University,
West Lafayette, IN 47907, xu972@purdue.edu. This work was in part presented at the 54th Annual Allerton Conference on
Communication, Control, and Computing, September 27-30, 2016, Monticello, IL, USA.

1

observation X of a signal matrix M of rank k, and may possess additional structure through the priors on
U and V .
Given the observed matrix X, the problem of interest is to reconstruct M , or at least detect that it exists.
For simplicity, we will work in the Bayes-optimal case where model parameters such as the true rank and
signal-to-noise ratio are known to the estimators. In the low signal-to-noise ratio regime we consider, exact
reconstruction of M is fundamentally impossible (see §2 for more details). Instead, we focus on the following
two tasks: first, detecting that the signal M exists, i.e., telling with high probability whether X was indeed
generated by the planted model as opposed to a null model where M = 0 and X consists only of noise; and
second, reconstructing M to some accuracy better than chance. We define these tasks formally as follows.
Definition 1 (Detection). Let P(X) be the distribution of X in the planted model (1), and denote by Q(X)
the distribution of X in the null model where X = W . A test statistic T (X) with a threshold  achieves
detection if limn→∞ [P(T (X) < ) + Q(T (X) ≥ τ )] = 0, so that the criterion T (X) ≥  determines with high
probability whether X is drawn from P or Q.
c=M
c(X) achieves reconstruction if EX kM
ck2 = O(n) and
Definition 2 (Reconstruction). An estimator M
F
ci ≥ , where hA, Bi = Tr A† B denotes the
there exists a constant  > 0 such that limn→∞ (1/n)EM,X hM, M
matrix inner product and kAk2F = hA, Ai.
For many natural problems in this class, it is believed that there is a phase transition, i.e., a threshold value
of snr below which both tasks are information-theoretically impossible: no test statistic can distinguish the
c = 0. This threshold is known as the
null and planted models, and no estimator can beat the trivial one M
information-theoretic threshold and it also depends on the structure of the problem, i.e., on the priors of U
and V ; if this prior is more strongly structured, we expect the threshold to be lower.
We focus on three cases of (1) which arise in many applications. In Sparse PCA, k = 1 and U = V = v
for some vector v. We further assume that v is sparse, with a constant fraction of nonzero entries. This
corresponds to the sparse, spiked Wigner model of [20, 38]. In Submatrix Localization (also known as
submatrix detection and noisy clustering), U = V and M contains k ≥ 2 distinct blocks of elevated mean.
This model arises in the analysis of social networks and gene expression, see e.g. [31, 15, 24]; it can also
be thought of as a Gaussian version of the stochastic block model [19, 18]. Finally, in Gaussian Mixture
Clustering, there are k ≥ 2 clusters, and each row of M is the center of the cluster to which the corresponding
data point belongs. This model has been widely studied, see, e.g., [47, 46, 30, 29, 2].
For each of these three problems, our goal is to compute the information-theoretic threshold, and understand how it scales with the parameters of the problem: for instance, the sparsity of the underlying signal or
the number of clusters. In particular, a simple upper bound on the information-theoretic threshold for each of
these problems is the point at which spectral algorithms succeed, i.e., the point at which the likely spectrum
of X becomes distinguishable from the spectrum of the random matrix W . The spectral thresholds for our
problems are well known from the theory of Gaussian matrices with low-rank perturbations. However, based
on compelling but non-rigorous arguments from statistical physics (e.g. [37, 36]), it has been conjectured
that when the signal is sufficiently sparse, or its rank (the number of clusters or blocks) is sufficiently large,
the information-theoretic threshold falls strictly below the spectral one.
In this paper, we prove upper and lower bounds on information-theoretic thresholds of all three problems,
determining the threshold within a multiplicative constant in interesting regimes. For sparse PCA, we
determine the precise threshold in the limit where the signal matrix is very sparse; similarly, for the submatrix
localization problem, we determine the threshold
when the number of blocks is large. For the clustering
√
problem, our bounds differ by a factor of 2 in the limit where the number of clusters is large. Moreover,
our results verify the conjecture that the information-theoretic threshold dips below the spectral one when the
signal is sufficiently sparse, or when the number of clusters or blocks is sufficiently large. This corresponds to
recent results [1, 9, 17, 23] showing that, in the stochastic block model, the information-theoretic detectability
threshold falls below the Kesten-Stigum bound above which efficient spectral and message-passing algorithms
succeed [19, 18, 39, 33, 14]. We consider this evidence for the conjecture that these problems posses a ‘hard
but detectable’ regime where detection and reconstruction are information-theoretically possible but take at
least exponential time. Although our computations are specific to these models, our proof techniques are
2

quite general and may be applied with mild adjustment to a broad range of similar problems. We present
our results in §2, an overview of our proof techniques in §3, and full proofs in in §4.
Since the initial posting of this paper as an arXiv preprint, a number of interesting papers [44, 43, 35] have
appeared, some extending or improving our results. Sharp lower bounds for sparse PCA were also obtained
recently in [43] using a conditional second moment method similar to ours. Complete, but not explicit,
characterizations of information-theoretic reconstruction thresholds were obtained in [34, 35] for sparse PCA
and submatrix localization through the Guerra interpolation technique and cavity method. However, their
characterization of reconstruction thresholds does not directly apply to detection.

2

Models and results

2.1

Sparse PCA

Consider the following spiked Wigner model, where the underlying signal is a rank-one matrix:
λ
X = √ vv † + W ,
n

(2)
i.i.d.

Here, v ∈ Rn , λ > 0 and W ∈ Rn×n is a Wigner random matrix with Wii ∼ N (0, 2) and Wij =
i.i.d.

Wij ∼ N (0, 1) for i < j. We assume v is drawn from the sparse Rademacher prior, although many alternatives
may be imposed. Specifically, for some γ ∈ [0, 1] the support of v is drawn uniformly from all

n
subsets
S ⊂ [n] with |S| = γn (when n is finite, we assume that γn is an integer). Once the support is
γn
chosen, each nonzero component vi is drawn independently and uniformly from {±γ −1/2 }, so that kvk22 = n.
When γ is small, the data matrix X is a sparse, rank-one matrix observed through Gaussian noise.
One natural approach for this problem is PCA: that is, diagonalize X and use its leading eigenvector vb
as an estimate of v. The threshold at which this algorithm succeeds can be computed using the theory of
random matrices with rank-one perturbations [8, 42, 11]:
√
(1) When λ > 1, the leading eigenvalue of X/ n converges almost surely to λ + λ−1 , and hv, vbi2 converges
almost surely to 1 − λ−2 ; thus PCA succeeds
√ in reconstructing better than chance;
(2) When λ ≤ 1, the leading eigenvalue of X/ n converges almost surely to 2, and hv, vbi2 converges almost
surely to 0; thus PCA fails to reconstruct better than chance.
Because the leading eigenvalue of W is 2 w.h.p., detection is only possible when λ > 1. Intuitively, PCA
only exploits the low-rank structure of the underlying signal, and not the sparsity of v; it is natural to ask
whether one can succeed in detection or reconstruction for some λ < 1 by taking advantage of this additional
structure. Through analysis of an approximate message-passing algorithm and the free energy, the following
conjecture was made in statistical physics [38, 34]:
Conjecture 1. Let the computational threshold be the minimum of λ so that reconstruction or detection can
be attained in polynomial-time in n for a given γ. There exists γ ∗ ∈ (0, 1) such that
(1) If γ ≥ γ ∗ , then both the information-theoretic and computational thresholds are given by λ = 1.
(2) If γ < γ ∗ , then the computational threshold is given by λ = 1, but the information-theoretic threshold
for λ is strictly smaller.
We derive the following upper and lower bounds on the information-theoretic threshold in terms of λ and γ,
and confirm that the threshold is λ = 1 when γ is relatively large and falls strictly below λ = 1 when γ is
sufficiently small. Throughout, we use
h(γ) = −γ log γ − (1 − γ) log(1 − γ)
to denote the entropy function, and W(y) for the root x of xex = y. All our logarithms are natural.
3

Theorem 1. Let
p
λupper = 2 h(γ) + γ log 2

1

r





1√
2γ
W
lower
2γ e
λ
=
r 


√


 4γ − log γ − 2.1 −2 log γ −

(3)
γ ≥ 0.6
e−41 /81 ≤ γ < 0.6
3
2

log



3e
1−γ



(4)

γ < e−41 /81 .

Then detection and reconstruction are information-theoretically possible when λ > λupper and are impossible
when λ < λlower .
In our proof, we give tighter lower bounds, but these are analytically convenient.
Note that λupper falls below the spectral threshold λ = 1 whenever γ ≤ 0.054, and λlower matches
the spectral threshold whenever γ ≥ 0.6. Hence, Theorem 1 proves Conjecture 1 on information-theoretic
threshold, albeit without pinning down γ ∗ exactly. In addition, in the limit γ → 0, both λupper and λlower
give an information-theoretic threshold of
p
(5)
λc = 2 (1 + oγ (1)) −γ log γ ,
determining the threshold fully in the limit where the low-rank matrix is very sparse. Independent of the
present work, and building on our preprint [10], Perry et al. [43] obtained the same tight threshold
√ in this
limit with a smaller error term. Previous work [16] had determined that threshold scales as λ = Θ( −γ log γ)
up to a constant factor.
In passing, we note that there is a very interesting line of work on exact or approximate support reconstruction for sparse PCA, i.e., estimating correctly or consistently the positions of non-zeros in v, in a regime
where the size of the support is sublinear in n (see e.g., [28, 5, 12, 32, 21] and references therein)1 . In an
influential paper [28], it was shown that while the estimate via the classical PCA is inconsistent, a simple
diagonal thresholding procedure consistently estimates v provided that v is sufficiently sparse. Assuming
λ = Θ(1), it is later proved in [5] that diagonal thresholding exactly recovers the support of v with high
probability if γ . 1/(n log n), and the information-theoretic threshold for exact support recovery is given by
γ  1/ log n up to a constant factor. In contrast, we focus on the regime where the size of the support is
linear in n, i.e., γ = Θ(1), and λ = Θ(1). In this regime it is impossible to correctly or consistently estimate
the support of v, and hence we instead focus on detection and reconstruction better than chance.

2.2

Submatrix Localization

In the submatrix localization problem, our task is to detect within a large Gaussian matrix a small block
or blocks with atypical mean. Let σ : [n] → [k] be a balanced partition, i.e. one for which |σ −1 (t)| = n/k
for all t ∈ [k], chosen uniformly from all such partitions. This terminology will recur throught the paper.
Construct a n × n matrix Y such that Yi,j = 1σ(i)=σ(j) . In the planted model,


µ
1
X=√
(6)
Y − J +W ,
k
n
where W is again a Wigner matrix and J is the all-ones matrix. In the null model, X = W . The subtraction
of J/k
model,
√ centers the signal matrix so that EX = 0 in both the null and planted models. In the planted
√
(µ/ n) (Y − J/k) is a rank-(k − 1) matrix with the largest (k − 1) eigenvalues all equal to µ n/k, making
X a Wigner matrix with a rank-(k − 1) additive perturbation. Matrices of this type exhibit the following
spectral phase transition:
√
be precise, those references mostly study the spiked Wishart model: X = (λ/ n)uv > + W , where u ∈ Rm with i.i.d.
N (0, 1) entries and W is a m × n Gaussian matrix with i.i.d. N (0, 1) entries; the results can be readily extended to the spiked
Wigner model.
1 To

4

√
(1) When µ > k, the k leading eigenvalues of X/√n converge to µ/k + k/µ almost surely;
(2) When µ ≤ k, the k leading eigenvalues of X/ n converge to 2 almost surely.
Hence, it is possible to detect the presence of the additive perturbation from the spectrum of X alone when
µ > k. We prove the following upper and lower bounds on the information-theoretic threshold:
Theorem 2. Let
r

upper

µ

µlower

log k
= 2k
k−1

2


 q
2 log(k−1)
= k
k−1
q



2 k log k − 11k log3/4 (k)

(7)
k=2
3 ≤ k ≤ exp(224 )

(8)

4

k > exp(22 ) .

Then detection and reconstruction are information-theoretically possible when µ > µupper and impossible
when µ < µlower .
Note that µupper dips below the spectral threshold µ = k when k ≥ 11, indicating a regime where
standard spectral methods fail but detection is information-theoretically possible. Also, Theorem
2 proves
√
the conjecture in [37] that as k → ∞, the information-theoretic threshold is given by µ = 2 k log k.
Previous work in submatrix detection and localization, also known as noisy biclustering, mostly focuses on
finding a single submatrix, see, e.g., [31, 15, 24] and the references therein. Notably, √
[17] considers a general
setting where the number of blocks k could grow with n, and proves that if µ ≥ c k log n for some large
constant c, then it is informationally
possible to exactly reconstruct the support of the planted submatrices
√
with high probability; if µ ≤ c0 k log n, then exact support reconstruction is informationally impossible. In
our setting, µ = Θ(1) and k = Θ(1), so it is impossible to consistently estimate the support and we instead
resort to detection and reconstruction better than the chance.

2.3

Gaussian Mixture Clustering

Finally, we study a model of clustering with limited data in high dimension.
P Let v1 , ..., vk be independently
and identically distributed as N (0, k/(k − 1) In,n ) , and define v = (1/k) s vs to be their mean. The scaling
of the expected norm of each vs with k ensures that Ekvs − vk22 = n for all 1 ≤ s ≤ k. For a fixed parameter
α > 0, we then generate m = αn points xi ∈ Rn which are partitioned into k clusters of equal size by
a balanced partition σ : [n] → [k], again chosen uniformly at random from all such partitions. For each
data point i, let σi ∈ [k]
p denote its cluster index, and generate xi independently according to Gaussian
distribution with mean ρ/n (vσi − v) and identity covariance matrix, where ρ > 0 is a fixed parameter
characterizing the cluster separation. We can put this in the form of model (1) by constructing an n × k
matrix V = [v1 , ..., vk ], an m × k matrix S with Si,t = 1σi =t , and setting
r 

ρ
1
X=
S − Jm,k V † + W,
(9)
n
k
i.i.d.

where Wi,j ∼ N (0, 1). In the null model, there is no cluster structure and X = W . The subtraction of
Jm,k /k once again centers the signal matrix so that EX = 0 in both models. The following spectral phase
transition follows from the celebrated BBP phase transition [8, 41]:
√
ρ
(1) When ρ α > k − 1, then the largest eigenvalue of (1/m)X † X converges to (1 + k−1
)(1 + k−1
ρα ) almost
surely; √
√
(2) When ρ α ≤ k − 1, then the largest eigenvalue of (1/m)X † X converges to (1 + 1/ α)2 almost surely.
√
Thus spectral detection is possible if ρ α > (k − 1).
We prove
√ the following upper and lower bounds on the information-theoretic threshold, which differ by
a factor of 2 when k is large.
5

Theorem 3. Let
r

ρ

upper

ρlower

k log k
=2
+ 2 log k
α
(p
1/α
k=2
= q 2(k−1) log(k−1)
k ≥ 3.
α

(10)
(11)

Then detection and reconstruction are possible when ρ > ρupper and impossible when ρ < ρlower .
p
We conjecture that in the limit k → ∞, the information-theoretic threshold is ρ = 2 k log k/α, but we
do not find a proof.
Most previous work in Gaussian mixture clustering focuses exact or near-exact reconstruction, see e.g., [46,
30]. As in the §2.1, a popular approach is PCA, which identifies the clusters based on the first k principal
components of the data matrix. It is shown in [47] that PCA allows identification of clusters with a cluster
√
separation ρ = Ω(k 1/4 log n) and a sample of size m = Ω(d3 log d). This technique was extended√to non√
Gaussian distributions [29, 2], and for Gaussian, the cluster separation is improved to be ρ = Ω( k log n)
and the sample complexity reduced to m = Ω(k 2 d) in [2]. In our setting, since ρ is a fixed constant, the
cluster separation is not sufficient for exact reconstruction and we turn to detection and reconstruction
better than chance. Somewhat surprisingly, we find that if the number of clusters is large, clustering is
informationally possible even when below the spectral phase transition threshold, and we conjecture that in
this regime it is computationally hard to identify the clusters. We note that a similar “hard-but-detectable”
regime has been determined empirically in [46].

3

Proof techniques

This section gives a brief overview of our proof techniques; the full proof will be presented in the next section.

3.1

The likelihood ratio and hypothesis testing

Detection is a classic hypothesis testing problem. Given a test statistic T (X), we consider its distribution
under the planted and null models. If these two distributions are asymptotically disjoint, i.e., their total
variation distance tends to 1 in the limit of large datasets, then it is information-theoretically possible to
distinguish the two models with high probability by measuring T (X). A classic choice of statistic for binary
hypothesis testing is the likelihood ratio,
P
P
P(X|M ) P(M )
P(X)
M P(X, M )
=
= M
.
Q(X)
Q(X)
Q(X)
This object will figure heavily in both our upper and lower bounds. By the Neyman-Pearson lemma [27], the
likelihood ratio is the most powerful test statistic of a given significance level; that is, if we set the threshold
 at the point such that Q(T (X) < ) = α for any fixed α, it maximizes P(T (X) ≥ ).
Our upper bounds do not use the likelihood ratio directly, since it is hard to furnish lower bounds on the
typical value of P(X)/Q(X) when X is drawn from P. Instead, we use the generalized likelihood ratio,
max
M

P(X|M )
.
Q(X)

In the planted model where the true underlying signal matrix is M0 , this quantity is trivially bounded below
by P(X|M0 )/Q(X). We will use simple first moment arguments to show that, with high probability in
the null model Q, this lower bound is not achieved by any M . An easy extension of this argument shows
c = argmaxM P(X|M ) has nonzero
that, in the planted model, the maximum likelihood estimator (MLE) M
correlation with M0 . Thus we can output a good estimate of M0 by exhaustive search.
6

The conditional likelihood ratio has a particularly elegant form when the noise is additive and Gaussian.
It is first useful to write down the probability distribution of a Wigner random matrix in the space of
symmetric matrices (also known as the Gaussian Orthogonal Ensemble) as
Q(W ) =

1 − 1 kW k2F
e 4
Zn

(12)

where Zn is a normalization constant depending only on n. Similarly, if W is a Gaussian random matrix
whose entries are independently distribution as N (0, 1), then
Q(W ) =

1 − 1 kW k2F
e 2
.
Zn0

(13)

Thus, for Wigner noise the conditional likelihood ratio is
2
2
2
1
1
1
P(X|M )
Q(X − M )
=
= e 4 (kXkF −kX−M kF ) = e 2 hX,M i− 4 kM kF
Q(X)
Q(X)

(14)

and identical for Gaussian noise except for a factor of two in the exponent.
The conditional log likelihood is a weighted sum of the entries of X, and is therefore itself Gaussian. Our
first moment bounds now proceed as follows. In the planted model, when X = M0 + W , the conditional log
2
likelihood of the planted signal M0 is 21 hW, M0 i + 41 kM0 kF . We can use standard Gaussian concentration
2
results to bound the typical deviation of this quantity around its mean of 41 kM0 kF . On the other hand, in
2
the null model where X = W , the conditional log likelihood of any M is 21 hW, M i − 14 kM kF , and we can
combine Gaussian concentration bounds with a union bound over all possible M to compute when, with
high probability in the null model, no M will beat the conditional log likelihood of the planted signal M0 .
As above, this argument can be nominally modified to show that the MLE estimate is positively correlated
with M0 . This technique must be altered slightly for the case of Gaussian Mixture Clustering, since M ∝ SV †
and V is chosen from a continuous prior. We could take a union bound over V by suitably discretizing; instead
we use the fact that for any S we can analytically maximize the conditional likelihood of SV † with respect
to V by setting the ith cluster center to be the empirical center of the data points assigned to cluster i by
S. This alters the distribution of the likelihood ratio, but we proceed analogously to above with the proper
concentration results.

3.2

Second moment bounds and contiguity

Intuitively, if the planted model P and the null model Q have asymptotically disjoint support, then the
likelihood ratio P/Q is almost always either very large or very small. In particular, its variance in Q must
diverge. This suggests that we can derive lower bounds on the threshold by bounding its second moment in
Q, or equivalently its expectation in P. Suppose the second moment is bounded by some constant C, i.e.,
"
2 #

 Z
P(X)
P(X)
P(X)2
EX∼Q
= EX∼P
=
dX
≤C.
(15)
Q(X)
Q(X)
Q(X)
X
This implies a bound on the Kullback-Leibler divergence between P and Q, since Jensen’s inequality gives
DKL (PkQ) = EX∼P log

P(X)
P(X)
≤ log EX∼P
≤ log C = O(1) .
Q(X)
Q(X)

(16)

Moreover, it also implies that detection is impossible. To see this, consider the following definition:
Definition 3. Let P = (Pn ), Q = (Qn ) be sequences of distributions defined on the same sequence of spaces
Ωn . We write P E Q, and say that P is contiguous to Q, if for any sequence of events E = (En ) such that
Q(E) → 0, we also have P(E) → 0.
7

If P E Q then detection is impossible, since no algorithm can return “yes” with high probability (or even
positive probability) in the planted model, and “no” with high probability in the null model.
The following simple argument shows that (15) implies P E Q and hence non-detectability. Let E be
a sequence of events such that Q(E) → 0, and let 1E denote the indicator random variable for E. Then
Cauchy-Schwarz gives
s
2

p
P(X)
P(X)
× EX∼Q 12E ≤ CQ(E) → 0 .
1E ≤ EX∼Q
(17)
P(E) = EX∼P 1E = EX∼Q
Q(X)
Q(X)
We note that showing that Q E P often requires additional arguments such as the small subgraph conditioning
method [40, 9].
The following lemma gives a general expression for the second moment of the likelihood ratio whenever
the model consists of a symmetric signal matrix with Wigner noise or an asymmetric signal matrix with
Gaussian noise.
Lemma 1. Let P(X) and Q(X) be the planted and null models X = M + W and X = W respectively, where
M is drawn from some prior over symmetric matrices and W is a Wigner matrix. Then

EX∼Q

P(X)
Q(X)

2

0

1

= EM,M 0 e 2 hM,M i ,

where M and M 0 are drawn independently from the prior. Similarly, if M is drawn from some prior over
asymmetric matrices and W is a Gaussian random matrix,

EX∼Q

P(X)
Q(X)

2

0

= EM,M 0 ehM,M i .

Thus the second moment method boils down to calculating an exponential moment of the correlation
between two independent draws from the prior P(M ). Depending on P(M ), these draws can correlate
in complicated ways, and the remainder of our second moment computations consist of combinatorially
analyzing the various events in P(M ) that give rise to these correlations.

3.3

Conditional second moment method

Sometimes, rare events can cause the second moment to explode even when two models are truly contiguous.
We circumvent this by computing the second moment conditioned on a sequence of high-probability events
F which rule out the catastrophic rare ones.
In the planted model, these events can occur both in the prior distribution of the planted signal, and in
the additive Gaussian noise of the channel. To address atypical events in the prior, we will condition on some
high probability property of the signal M , choosing an appropriate event {M ∈ F } such that P(F ) = 1+o(1),
and form the corresponding conditional distribution
P0 (X) =

EM [P(X|M )1F ]
.
P(F )

(18)

The case where the problematic events occur in the noise distribution is similar; we define an event {X −M ∈
FM } such that P(FM |M ) = 1 + o(1) uniformly over M , and the corresponding conditional distribution
P0 (X) = EM [P0 (X|M )],

where

P0 (X|M ) =

P(X|M )1FM
.
P(FM |M )

(19)

In both cases, it is straightforward to show that P E P0 , and therefore that if the conditional second moment
2
EX∼Q (P0 (X)/Q(X)) is bounded, then P E P0 E Q.

8

In the Gaussian mixture clustering problem, we use the first type of conditional second moment method
by conditioning on the typical value of cluster centers kV k2 . In the sparse PCA problem and the submatrix
localization
problem, we instead use the second type of conditional second moment method to close the factor
√
of 2 between the direct second moment lower bound and the first moment upper bound. A similar method
was used in [43] to derive the sharp constant of the detection lower bound in the sparse PCA problem.
Previous work [6, 49] used the conditional second moment method in deriving the sharp detection threshold
in community detection problem.
As a high-level motivation for this conditioning, let P(X) and Q(X) be the planted and null models
X = M + W and X = W respectively, where M is drawn from some prior over symmetric matrices and W
is a Wigner matrix. Using Fubini’s theorem,

EX∼Q

P(X)
Q(X)

2


P(X|M )P(X|M 0 )
Q2 (X)
h 1
i
2
0 2
0
1
1
= EM,M 0 EX∼Q e− 4 kM kF − 4 kM kF + 2 hX,M +M i


= EM,M 0

1

= EM,M 0 e 2 hM,M

0

i

where M and M 0 are drawn independently from the prior, and in the last line we have carried out the
the integration with respect to X ∼ Q directly. The reader may refer to the proof of Lemma 1 for the
intervening lines. However, it is possible to decrease the second moment by conditioning on the typical value
of hX, M + M 0 i in the planted model.


Specifically, suppose that P hX, M i ≈ kM k2F | M = 1 + o(1) uniformly over M . Then, by letting
FM = {hX, M i ≈ kM k2F }, we get that

EX∼Q

P0 (X)
Q(X)

2





1
1
1
2
0 2
0
≈E
EX∼Q exp − kM kF − kM kF + hX, M + M i 1{FM } 1{FM 0 }
4
4
2




1
1
1
≈ EM,M 0 EX∼Q exp − kM k2F − kM 0 k2F + hX, M + M 0 i 1{hX,M +M 0 i≈kM k2 +kM 0 k2 }
F
F
4
4
2
!#
"


2
kM + M 0 k2F
kM k2F + kM 0 k2F
1
hM, M 0 i −
1−
≈ EM,M 0 exp
2
4
kM + M 0 k2F
+



2
0 2
kM
k
+
kM
k
1
F
F
= EM,M 0 exp hM, M 0 i
2
kM + M 0 k2F



where we used the fact that for Y ∼ N (0, σ 2 ), E eY 1{Y ≤b} ≤ exp 12 σ 2 − 12 σ 2 (1 − σb2 )2+ and 12 hX, M +
M 0 i ∼ N (0, kM + M 0 k2F /2). Comparing
 this conditional second moment with the unconditional one, there
is a correction term kM k2F + kM 0 k2F /kM + M 0 k2F , which is most effective if M = M 0 . It will turn out
that in the sparse PCA problem, when the sparsity γ → 0 or in the submatrix localization problem, when
the number of blocks k → ∞, the second moment is dominated by the event that M = M 0 . Hence,
M,M 0


EX∼Q

P0 (X)
Q(X)

2



1
2
≈ exp kM kF PM,M 0 [M = M 0 ] ,
4


as opposed to exp 21 kM k2F PM,M 0 [M = M 0 ] in the absence of conditioning, a factor of two gain in the
exponent. Notice that there is one slight difference between this informal description and our proofs. Instead
of conditioning on the typical value of hX, M i ≈ kM k2F , we condition on the typical value of k(X − M )S k2 ,
where S = supp(M ) and XS denotes the matrix by setting entries of X outside of S to be zero. The reader
may refer to Section 4.2.3 and Section 4.3.3 for details.

9

3.4

Non-reconstructibility

Without further embellishment, contiguity is a statement about detection and not reconstruction. It is
tempting to believe that whenever contiguity holds—that is, whenever we cannot tell whether a particular
sample was generated from the null or planted model—we also cannot infer the planted signal M0 better
than chance. This is not the case. Consider a strange situation in which the null and planted models are
identical and noiseless: in P we observe X = M0 drawn from a prior P0 , and in Q we observe a random draw
M from P0 . Detection is patently impossible because these models are contiguous, but if we know that X is
drawn from the planted model, the reconstruction problem is trivial since we observe the ground truth M0
directly.
However, in the model described by (1) where the noise is additive and Gaussian, we can show that a
bounded KL divergence implies that reconstruction is impossible as well. If M is the planted signal, the
c is EkM − M
ck2 . The following theorem shows that whenever the
mean squared error of an estimator M
F
c
KL divergence DKL (PkQ) = o(n), the estimator M that minimizes the mean squared error tends to the
c = 0. By (16) a bounded second moment (15) implies a bounded KL divergence; hence
trivial estimator M
a bounded second moment also implies non-reconstruction.
Theorem 4. Let P(X) and Q(X) be the planted and null models X = M + W and X = W respectively,
where M is drawn from some prior such that E[M ] = 0 and limn→∞ (1/n)E[kM k2F ] exists, and where W
is a Gaussian or Wigner matrix. The MMSE estimator in the planted model is the mean of the posterior
b
distribution: E(X)
= E[M |X]. If the KL divergence DKL (PkQ) = o(n), then
lim inf
n→∞

1
2
b
EX∼P kE(X)k
F = 0.
n

(20)

c=M
c(X) such that EX kM
ck2 = O(n), we have that
It further follows that for any estimator M
F
lim inf
n→∞

1
ci = 0.
EM,X hM, M
n

(21)

√
When M = (snr/ n) U V † , where the rows of U and V are independently and identically distributed according to some priors, then the liminf in (20) and (21) can be replaced by lim.
In cases where we use the conditional second moment method by conditioning on events F that depend
only on the signal M , i.e., F = {M ∈ F }, the conditional distribution P0 given in (18) is still an additive
Gaussian model. Hence, we can still apply Theorem 4 with P0 and Q, concluding that a bounded conditional
2
second moment EX∼Q (P0 (X)/Q(X)) implies non-reconstruction in P0 and hence non-reconstruction in P.
When we need to condition on events FM that depend on both M and X, i.e., F = {X − M ∈ F },
the conditional distribution P0 given in (19) may no longer be an additive Gaussian model, and hence Theorem 4 cannot be directly invoked. Fortunately, we are able to prove that (1/n)DKL (P0 kQ) is an asymptotic upper bound to (1/n)DKL (PkQ). As a consequence, by (16) a bounded conditional second moment
2
EX∼Q (P0 (X)/Q(X)) implies DKL (PkQ) = o(n) and hence non-reconstruction in P by invoking Theorem 4.
Let kM k∗ denote the nuclear norm of M , which equals to the sum of all the singular values of M .
Theorem 5. Let P(X) and Q(X) be the planted and null
√ models X = M +
√W and X = W respectively,
where M is drawn from some prior such that kM k2 = O( n) and kM k∗ = O( n) uniformly over all M , and
where W is a Gaussian or Wigner matrix. Suppose P0 is given in (19) with P(FM |M ) = 1 + o(1) uniformly
over all M . Then
DKL (PkQ) ≤ DKL (P0 kQ) + o(n).
√
√
Theorem 5 needs the technical assumptions that kM k2 = O( n) and kM k∗ = O( n). These assumptions
are satisfied in the sparse PCA and submatrix localization problems, but not in the Gaussian mixture
clustering problem, which has a prior distribution of unbounded support. This last fact does not impact
our results, because the conditioning we emply for the clustering lower bound is on the signal M and not
the noise, meaning that as above we can invoke Theorem 4. To deal with prior distribution of unbounded
support, one could emply a truncation argument.
10

4
4.1

Proofs
Notation and preliminary lemmas

We begin by proving Lemma 1. The proof is discussed in [26, p.97]; we give the full proof here for completeness.
Proof of Lemma 1. We focus on the Wigner noise case as the proof for Gaussian noise case is identical except
for a factor of 2. As we noted in equation (14), the conditional likelihood ratio is
2
1
1
Q(X − M )
P(X|M )
=
= e 2 hX,M i− 4 kM kF .
Q(X)
Q(X)

(22)

We have P(X) = EM P(X|M ). Reversing the order of the expectations and applying (14) gives
EX∼Q

P(X|M ) P(X|M 0 )
P(X)2
0
=
E
E
X∼Q
M,M
Q(X)2
Q(X)2
P(X|M ) P(X|M 0 )
= EM,M 0 EX∼Q
Q(X)2
1

2

0 2
kF )

1

2

0 2
kF −kM +M 0 k2F )

= EM,M 0 e− 4 (kM kF +kM
= EM,M 0 e− 4 (kM kF +kM
1

1

EX∼Q e 2 hX,M +M

0

i

0

= EM,M 0 e 2 hM,M i ,
2

where in the second-to-last line we used the moment generating function EX∼Q ehX,Ai = ekAkF . This completes the proof.
In the submatrix localization and Gaussian mixture clustering problems, the underlying low-rank signal
matrix M arises from a balanced partition σ0 : [n] → [k]. In these cases we can equivalently frame results
about reconstruction in terms of how well we can infer this original partition. Given σ0 and an estimated
partition σ
b, we define the overlap matrix as a k × k matrix ω(σ0 , σ
b) which has s, t entry equal to the fraction
of integers in [n] assigned by σ0 to group s and by σ
b to group t, i.e.
ω(σ0 , σ
b)s,t =

|σ0−1 (s) ∩ σ
b−1 (t)|
n/k

and we drop the dependence on σ0 and σ
b whenever clear. Our assumption that the partitions are balanced
implies that ω is doubly stochastic.
We can read off scalar measures of the correlation between two partitions σ and τ —i.e. of how well we
have reconstructed the planted signal—directly from ω; two will be particularly useful. It is typical in the
literature to work with what we will call the trace overlap between σ and τ , T (σ, τ ) := maxπ Tr πω(σ, τ ),
where the maximum is taken over all permutation matrices. In our problems, however, it is analytically more
2
convenient to use L(σ, τ ) := kω(σ, τ )kF , which we call the L2 overlap. Both L(·) and T (·) range from 1,
when the two partitions are uncorrelated and ω = J/k, to k, when they are identical up to a permutation of
the group labels, and ω is the corresponding permutation matrix. The following lemma states that whenever
the L2 overlap is bounded above 1, the trace overlap is as well.
Lemma 2. For any doubly stochastic matrix ω, L(ω) ≤ T (ω).
Proof. This lemma is an immediate consequence of Birkhoff’s theorem. We simply expand ω =
a convex combination of permutation matrices π and observe that
X
L(ω) = Tr ω † ω =
aπ Tr π † ω ≤ max Tr π † ω = T (ω),
π

π

the final inequality following from

P

π

aπ = 1.
11

P

π

aπ π as

Thus, to show that an estimator σ
b achieves trace overlap with the planted partition σ0 bounded above one,
it is sufficient to show that L(b
σ , σ0 ) > 1.
Finally, in the submatrix localization and Gaussian
mixture clustering
problems, our second moment


calculations will reduce to the computation of Eσ,τ exp(ξ(kωk2F − 1))/2 where the expectation is over uniformly random pairs of balanced partitions σ and τ with overlap matrix ω, and ξ is a parameter corresponding
to the signal-to-noise ratio. By [3, Lemma 6], it is straightforward to prove the following lemma giving a sufficient condition to guarantee that this expectation, and therefore the second moment as a whole, is bounded
by a constant. We will state the lemma in notation consistent with [3] and discuss afterwords.
Lemma 3. Assume that ϕ(ω) is an R-valued function of doubly-stochastic k×k matrices ω with the properties
that ϕ(J/k) = 0 and for some δ > 0 and every k × k doubly stochastic matrices ω,

H(ω) + ϕ(ω) ≤ H(J/k) + ϕ(J/k) − δ kωk2F − 1 .
Then there exists a constant C, dependent on k and δ, such that
i
h
Eσ,τ enϕ(ω) ≤ C.
Proof. Let Ω = (Ωst ) such that Ωs,t = |σ −1 (s) ∩ τ −1 (t)|. Then ω = kΩ/n. Denote by D the set of all k × k
matrices Ω = (Ωst ) of nonnegative integers such that
Q the sum of each row and each column is n/k. Notice
that for a given Ω = (Ωst ), there are precisely n!/ s,t Ωs,t ! pairs of balanced partitions (σ, τ ) with overlap
matrix given by Ω. Hence,
h
i (n/k)!2k X
n!
Q
exp (nϕ(ω))
Eσ,τ enϕ(ω) =
n!2
s,t Ωs,t !
≤ k −2n

Ω∈D
2k k−1

e n
2πk k

X

n!
exp (ϕ(ω)) ,
s,t Ωs,t !

Q
Ω∈D

(23)

√
√
where we have used Stirling’s approximation 2πn(n/e)n ≤ n! ≤ e n(n/e)n in the last step. In view of the
assumption and [3, Lemma 6], there exists a constant C 0 > 0 dependent on δ and k such that
n
X
C0 
n!
C0
Q
enϕ(ω) ≤ k−1 k 2 eϕ(J/k) = k−1 k 2n .
n
n
s,t Ωs,t !
Ω∈D

Combing the last displayed equation with (23) yields that
h
i C 0 e2k
:= C,
Eσ,τ enϕ(ω) ≤
2πk k
which completes the proof.
Let us unpack
 the conditions of the above lemma in the context of our problems. For us, ϕ(ω) =
(ξ/2) kωk2F − 1 , and since H(J/k) = log k and kJ/kk2F = 1, it is in fact sufficient to study the function
Φ(ω) = H(ω) − log k +


ξ
kωk2F − 1 .
2

(24)


In particular, the hypotheses of Lemma 3 are satisfied provided that Φ(ω) ≤ −δ kωk2F − 1 for every doubly
stochastic matrix ω and some δ > 0. This is the case whenever ξ is sufficiently small. On the other hand,
in the limit ξ → ∞, Φ(ω) is maximized by any permutation matrix, the doubly stochastic matrices with
maximal Frobenius norm and minimal entropy. It has been conjectured that, for general ξ, the maximizer
is a convex combination of J/k and a permutation matrix, but this has not been proved.
The precise value of ξ up to which Φ(ω) is maximized by ω = J/k is not known. Fortunately, Achlioptas
and Naor, in their second moment lower bound on the k-colorability threshold for Erdős-Rényi graphs [3],
proved an upper bound on Φ by relaxing to singly stochastic matrices.
12

Lemma 4. [3, Theorems 7,9] When ξ < 2 log(k − 1)/(k − 1), argmax Φ(ω) = J/k.
One can obtain an even tighter bound in the special case k = 2. Recall that the 2×2 doubly stochastic matrices are a one-parameter family—since the upper left entry uniquely determines the matrix. Consequently
we can rewrite Φ(ω) in (24) as
ξ
Φ(x) = h(x) + (4x2 − 4x + 1) − log 2 .
2
The second derivative of Φ(x) is 4ξ − 1/(x(1 − x)). Hence, if ξ < 1, then Φ(x) is strictly concave in x and
arg maxx Φ(x) = 1/2.
Lemma 5. When k = 2 and ξ < 1, arg maxω Φ(ω) = J/2.

4.2

Sparse PCA

In this section we prove Theorem 1. First, we show that detection and reconstruction are possible if λ >
λupper using a first moment argument as described in Section 3.1: specifically, if λ > λupper then with
high probability in Q there are no v with likelihood as high as that of the ground truth v0 , and with high
probability in P all such v are correlated with v0 . Then, we prove that the second moment of the likelihood
ratio is bounded if λ < λlower ; as discussed in Section 3.2, this implies that detection and reconstruction are
impossible if λ < λlower .
4.2.1

First moment upper bound for sparse PCA
√
Recall that X = (λ/ n)v0 v0† +W , where v0 is drawn uniformly from V = {v ∈ {±γ −1/2 , 0} : |supp(v)| = γn}
and W is a Wigner matrix. For any v ∈ V, using (14), the conditional log likelihood ratio is
log

P(X|v)
1
1
= hM, Xi − kM k2F
Q(X)
2
4
1 λ2
1 λ
kvk42
= √ hv, Xvi −
2 n
4 n
1 λ
λ2 n
= √ hv, Xvi −
.
2 n
4

In the null model, X = W and hv, Xvi is distributed as N (0, 2n2 ), giving
 2

P(X|v)
λ n λ2 n
log
∼N −
,
.
Q(X)
4
2

(25)

On the other hand, in the planted model
λ
λ
hv, Xvi = hv, W vi + √ hv, v0 v0† vi = hv, W vi + √ hv, v0 i2 ,
n
n
so the conditional log likelihood has a distribution which depends on the inner product between v and the
ground truth v0 . We write this inner product as hv, v0 i = θn, for θ ∈ [−1, 1] so that


(2θ2 − 1)λ2 n λ2 n
P(X | v)
∼N
,
log
Q(X)
4
2
Whenever θ = 0 so that v is uncorrelated with v0 , this distribution is identical to that in the null model.
To show that detection is possible above (3), notice that in the planted model the maximum likelihood
estimate vb = argmaxv∈V P(X|v) has conditional log likelihood at least as large as the ground truth v0 . By
standard Gaussian tail bounds and setting θ = ±1 above,


p
P(X|v0 )
λ2 n
P log
≤
− O( n log n) ≤ n−Ω(1) .
Q(X)
4
13

In the null model, Gaussian tail bounds give us


 2

p
p
P(X|v)
λ2 n
λ n
Q log
≥
− O( n log n) ≤ exp −
+ O( n log n) .
Q(X)
4
4


n
n
Taking the union bound over all 2γn γn
possible v and invoking Stirling’s formula γn
≤ enh(γ) , we have




√
2
p
P(X|v)
λ2 n
n − λ 4n +h(γ)+γ log 2 +O( n log n)
Q max log
.
≥
− O( n log n) ≤ exp
v∈V
Q(X)
4

(26)

When this expression is e−Ω(n) , we can with high probability distinguish the null and planted models with
the generalized likelihood test. This occurs when λ < λupper where λupper is defined in (3), i.e.,
λ2
> h(γ) + γ log 2 .
4

(27)

Next, we prove that reconstruction is also possible above this bound. Suppose that X is generated from
the planted model, and that hb
v , v0 i = θn. We bound the probability that vb has conditional log likelihood
as large as v0 with a union bound over vb correlated with v0 , but we bound the number of such vectors
n
generously as 2γn γn
once again. Combining this with the Gaussian tail bound and invoking Stirling gives

p
P(X|v)
λ2 n
>
+ O( n log n)
Q(X)
4
v∈V:hv,v0 i≤θn
 


p
(2θ2 − 1)λ2
≤ exp n
+ h(γ) + γ log 2 + O( n log n) .
4


P

max

log

Since the coefficient of n in the exponent is an analytic function of θ, whenever (27) holds, the RHS of
the last displayed equation is exponentially small unless θ2 > ε for some constant ε > 0. Therefore,
with high probability the MLE estimator has overlap (hb
v , v0 i/n)2 = θ2 > ε > 0 with the ground truth.
√
†
2
4
2
c, M i =
c = (λ/ n)b
ck = (λ /n)kb
v k2 = λ2 n; moreover, with high probability hM
Moreover, if M
v vb , then kM
F
2
2
2
c
(λ /n)hb
v , v0 i > ελ n. Hence, the estimator M reconstructs the signal matrix better than chance.
4.2.2

Second moment lower bound for sparse PCA

In this subsection, we use the second moment method to prove a lower bound on the detectability transition
for sparse PCA. We assume λ < 1 throughout√the proof; the boundary case λ = 1 is not addressed. In the
planted model, the signal matrix is M = (λ/ n)vv † , and in the null model it is zero. In both cases, we
have X = M + W where W is a Wigner noise matrix. Applying Lemma 1, the second moment (where X is
drawn from the null model) is

EX∼Q

P(X)
Q(X)

2

λ2

2

= Ev,w e 2n hv,wi ,

(28)

where v and w are drawn independently from the prior.
Denote the overlap z = |supp(v) ∩ supp(w)| and let t be the difference between the number of indices in
that intersection where v and w agree and the number of indices where they disagree. In that case,
hv, wi =

t
.
γ

Then, z follows an hypergeometric distribution with parameter (n, γn, γn) and given z, t is distributed as a
sum of z independent Rademacher random variables. If we write
η = λ/γ ,
14

(29)

then

EX∼Q

P(X)
Q(X)

2

 2 2
η t
= Et e 2n .

We know from [4, p.173] that z has the same distribution as the random variable E[z|Bn ] where z is a Binomial
random variable with parameters (γn, γ) and Bn some suitable σ-algebra. Given z, let t be distributed as a
sum of z independent Rademacher variables.
Lemma 6. Let (i )i≥1 denote a sequence of independent Rademacher random variables. For anyPa > 0, let
z
g be the piecewise linear function on [1, ∞) such that, for any positive integer z, g(z) = E exp[a( i=1 i )2 ].
Then, the function g is convex.
Proof. Since g is convex and continuously differentiable on each interval of the form (z, z + 1) where z is an
integer, we only have to prove that its left derivative is less or equal
its right derivative at z + 1. This is
Pto
z
equivalent to showing that g(z + 2) + g(z) ≥ 2g(z + 1). Define u = i=1 i . Conditioning with respect to u,
2
2
we obtain g(z + 1) = Eu [eau +a cosh 2au] and g(z + 2) = Eu [eau [0.5e4a cosh 4au + 0.5]. Hence, it suffices to
prove that, for any u,
1
3
ea cosh 2au ≤ e4a cosh 4au + .
4
4
√
For x ≥ 0, let h(x) = eax cosh(2au x). Since h is a product of two increasing convex functions, h is also
convex. This implies the above inequality and concludes the proof.
By Jensen’s inequality, it follows that

EX∼Q

P(X)
Q(X)

2

 2 2
η t
≤ Et e 2n .

(30)

To simplify the notation, we simply write z and t instead of z and t in the sequel. Note that
 22
 X
z
η t
η 2 u2
Et e 2n | z =
e 2n (Pt [|t| ≥ u | z] − Pt [|t| ≥ u + 1 | z])
u=0

≤1+

z
X
η 2 u η 2 u2
e 2n Pt [|t| ≥ u | z]
n
u=1

≤1+2



z
X
η 2 u u22 ηn2 − z1
,
e
n
u=1

where we applied Hoeffding’s inequality: Pt (|t| ≥ u | z) ≤ 2e−u
We consider three subcases depending on the value of z.
Case 1: If z ≤ (n/η 2 )λ,
 22

η t
Et e 2n | z
≤
≤
where we used z ≤

nλ
η2

2

/(2z)

(31)
(32)

in the last line.

Z ∞ 2 −u2  η2 


z
X
η 2 u u22 ηn2 − z1
η u 2 z1 − n
e
≤ 1 + O(1)
e
du
n
n
0
u=1




η2
1
≤
O
,
O(1) 1 +
n/z − η 2
1−λ
1+2

in the last inequality.

15

(33)

Case 2: If (n/η 2 )λ < z ≤ n/η 2 , we have

  22

η t
2n
n
n
Ez Et e
| z 1z∈( 2 λ, 2 ]
η

η

"

!
#


z
X
η 2 u u22 ηn2 − z1
≤ Ez
1+2
1z∈( n2 λ, n2 ]
e
n
η
η
u=1



η 2 (z + 1)2
≤ Ez
1+
1z∈( n2 λ, n2 ]
n
η
η
h
i
≤ O(1 + nγ)Pz z ≥ ηn2 λ ,


where in the second inequality we bound exp u2 /2 η 2 /n − 1/z ≤ 1 and in the third inequality we use
z ≤ n/η 2 and z ≤ nγ. Since λ/η 2 = γ 2 /λ > γ 2 and z ∼ Bin(γn, γ), Bernstein’s inequality implies that
Pz z ≥ (n/η 2 )λ is exponentially small. Therefore,

  22 
η t
(34)
Ez Et e 2n |z 1z∈( n2 λ, n2 ] = o(1) .
η

η


Case 3: Finally, if n/η 2 < z ≤ γn, then exp u2 /2 η 2 /n − 1/z is exponentially large in u. Thus to show
that the second moment is finite, we need to use the fact that Pz [z ≥ a] for a > n/η 2 is exponentially small.
When z > n/η 2 , the bound in(32) implies that


 22
 2 2
z
X
η t
z2 η2
z
η2 u
z η
z
Et e 2n | z ≤ 1 + 2e 2n − 2
≤ O(n) exp
−
,
n
2n
2
u=1
where we applied z ≤ γn and the second inequality holds due to λ < 1. For any 0 < p0 < p1 ≤ 1, define


1 − p1
p1
hp0 (p1 ) = p1 log( p0 ) + (1 − p1 ) log
,
(35)
1 − p0
the KL-divergence between Bernoulli random variables with parameters p0 and p1 respectively. Chernoff’s
inequality implies that for any a ≥ γ 2 n,

 
a
.
Pz [z ≥ a] ≤ exp −γnhγ
γn
As a consequence,
  22


η t
Ez Et e 2n | z 1z∈( n2 ,γn]

≤

O(n)

η

γn
X


exp

z=n/η 2

"
≤

2

O(n ) exp n

z
z2 η2
− − γnhγ
2n
2
#

sup



z
γn



ψ(ζ) ,

ζ∈[1/η 2 ,γ]

where
(η 2 ζ − 1)ζ
(η 2 ζ − 1)ζ
ψ(ζ) =
− γhγ (ζ/γ) =
− ζ log
2
2

 


ζ
γ−ζ
− (γ − ζ) log
+ γ log(γ) ,
γ
1−γ

(36)

Then, we need to show that
ψ(ζ) < 0

for all
2

ζ ∈ [γ 2 /λ2 , γ] ,

(37)
2

Note that this property is trivial when γ/λ > 1 so that we may restrict our attention to γ/λ ≤ 1. Since
λ < 1, it follows that ψ(γ 2 /λ2 ) = −γhγ (γ/λ2 ) < 0. For ζ = γ, ψ(ζ) = (λ2 − γ)/2 − γ log(1/γ) , which is
negative for
p
λ < 2γ(− log γ + 1/2) .
(38)
16

λ
1.0
0.8
0.6
0.4
0.2
0.05

0.10

0.15

0.20

0.25

0.30

γ

Figure 1: Upper and lower bounds on the information-theoretic detectability threshold in sparse PCA.
Our upper bound (dashed) shows that the detectability threshold is strictly below the spectral threshold
λ = γη = 1 for γ < 0.054. The solid line shows the lower bound given by (37), and the dotted line shows
the simpler lower bound given√by (40). Notice that the solid line is not touching the dashed line even in the
limit γ → 0; there is a gap of 2.
Moreover, the second derivative of ψ has at most two roots. It follows that ψ(ζ) can have at most three
local minima or maxima occurring at the roots of


ζ(1 − γ)
1
0
2
.
ψ = η ζ − − log
2
γ(γ − ζ)
Figure 1 shows λ as a function of γ, illustrating in particular that it rapidly approaches the spectral transition
λ = 1 as γ approaches 1.
We now derive an analytic bound of ψ. For ζ ∈ (γ 2 /λ2 , γ],
 


η2 γ − 1
ζ
1−γ
ψ(ζ) ≤ ζ
− ζ log
+
γ(1
−
ζ/γ)
log
2
γ2
1 − ζ/γ


2
η γ−1
ζ
≤ζ
− ζ log
+ ζ − γ2
2
γ2

 2
λ /γ + 1
+ 2 log λ ,
≤ζ
2
2
2
2
where we used log(1
line and
 + x) ≤2x2 in the
 second

 ζ ≥ γ /λ ≥ γ in the third line.
Therefore, Ez Et exp η t /2n | z 1z∈(n/η2 ,γn] , and hence the second moment, are bounded as long as

log λ2 +

λ2 /γ + 1
< 0.
2

If, for any y > 0, we use W(y) to denote the root x of xex = y, (39) holds whenever
s


1
λ < 2γW √
.
2 eγ
As y → ∞, we have W(y) ∼ log y. Thus as γ → 0, this lower bound approaches
s
1
lower
λ
∼ 2γ log √ .
2 eγ
17

(39)

(40)

(41)

Let us now turn to regime γ > 0.6, where we will show the second moment is bounded whenever λ < 1.
In view of (33) and (34), it suffices to prove that


  22
η t
Ez Et e 2n | z 1z∈(γ 2 n,γn] = O(1) ,
whenever λ < 1. From (31), we have
  22


η t
2n
Ez Et e
| z 1z∈(γ 2 n,γn]
"
#
z
X
η 2 u η 2 u2
≤ Ez 1 +
e 2n Pt [|t| ≥ u | z] 1z∈(γ 2 n,γn
n
u=1
 
γn X
z
X
(a)
γn z
η 2 u η2 u2
γ (1 − γ)γn−z
≤ 1+
e 2n Pt [|t| ≥ u | z]
z
n
z=γ 2 n u=1
 2


 
γn X
z
X
(b)
(1−λ2 )u2
η2 u
u
u
1
z
− 2nγ 2
p
≤ 1 + O(1)
e
exp
+ zh
+
− z log(2) − γnhγ
,
2
2nγ
2z
2
γn
(z(1 − z/γn)) ∨ 1
2 u=1 n
z=γ n

where we used in (a) that z follows a Binomial distribution. In step (b), hγ is defined as in (35), and we
have used the facts that





u+z
u+z
≤ 2 exp −zh1/2
Pt [|t| ≥ u | z] = 2 Pr Bin(z, 1/2) ≥
2
2z
and
 
γn
≤
z

!

 
z
p
∧ 1 exp γnh
γn
2πz(1 − z/(γn))
1



for z ≤ γn.
Expanding as Taylor series, we have
4
h(u) ≤ log(2) − 2(u − 1/2)2 − (u − 1/2)4
3

and hγ (u) ≥

(u − γ)2
.
2γ(1 − γ)

This yields

  22 
η t
Ez Et e 2n |z 1z∈(γ 2 n,γn]
≤ 1 + O(1)

γn X
z
X
z=γ 2 n

u=1

η2 u
n

p

(z(1 − z/γn)) ∨ 1

e

−

(1−λ2 )u2
2nγ 2





2
2
4
2
u
u
u
(z/(γn)
−
γ)

expn
−
−
−
2(γn)2
2zn 12z 3 n
2(1 − γ)
|
{z
}
= (I)


We focus on the term (I), which is maximized with respect to u by choosing


1
1
1
u2 = × 12z 3 n
−
.
2
2γ 2 n2
2zn

18

Hence,

2
1 γn
(z/(γn) − γ)2
3 z3
−
−
2
3
4γ n
γ
z
2(1 − γ)


2
3z
1
z
≤
−
−γ
4γ 2 n 2(1 − γ)
γn


2
3
1
z
≤
−
−γ
,
4γ
2(1 − γ)
γn

(I) ≤

since z ≤ γn. The above expression is negative as soon as γ > 0.6. For such a choice of γ, there exist two
positive constants c1 and c2 such that
  22 

γn X
z
X
(z−γ 2 n)2
η t
u2
u
2n
p
e−c1 n e−c2 n
Ez Et e
|z 1z∈(γ 2 n,γn] ≤ 1 + O(1)
= O(1) ,
n (z(1 − z/γn)) ∨ 1
z=γ 2 n u=1
where the last equality holds because
γ > 0.6.

Pz

u=1 (u/n)e

−c1 u2 /n

= O(n). This completes the proof in the regime

The conclusion for reconstruction follows by applying (16) and Theorem 4. Furthermore, for any estimator
c = (λ/√n)b
vb ∈ V of v, applying Theorem 4 to the estimator M
v vb† gives
1
1
ci = o(1) .
Ehv, vbi2 =
EhM, M
n2
nλ2
Thus we can neither reconstruct the signal matrix nor the sparse vector v.
4.2.3

Conditional second moment lower bound for sparse PCA

Bounding the second moment is too rough
to pinpoint the exact information-theoretical threshold for small
√
γ. Indeed, there is asymptotically an 2 gap between the λlower and λupper . To recover the exact constant,
we shall bound some conditional second moment. Throughout this proof, we consider λ such that
s
"  
 

#
 
1
1
3e
3
1
2
λ < 4γ log
− 2.1 2 log
− log
≤ 4γ log
.
(42)
γ
γ
2
1−γ
γ
We shall restrict our attention to γ small enough that log(1/γ) > 41 + log(81), which is equivalent to
s


1
√
.
(43)
9 γ < 2γW √
2 eγ
For any set a ⊂ [n] and any square matrix X, let Xa refer to the matrix whose entries outside a × a have
been set to zero. Given a vector v, we define the event Γv by


λ
√
†
Γv := k(X − √ vv )supp(v) k2 ≤ 2.1 nγ .
(44)
n
Under P(·|v), the supp(v) × supp(v) submatrix of X − √λn vv † is distributed as a Wigner Matrix. By [7,
√
Theorem 5.1], its spectral norm rescaled by γn converges almost surely to 2 when n → ∞, and so P(Γv |v) =
1 + o(1) uniformly with respect to v. The event Γv means that the noise added to the nonzero entries of vv †
is not uncharacteristiaclly large.

19

Next, we condition on the high probability events Γv and define the conditional probability distribution


1Γv
0
.
(45)
P (X) = Ev P(X|v)
P(Γv |v)
The conditional second moment decomposes as
 02




P (X)
P(X|v)P(X|w)
1Γv 1Γw
EX∼Q
=
E
E
v,w
X∼Q
Q2 (X)
Q2 (X)
P(Γv |v)P(Γw |w)




†
†
λ
λ2 n
√
<vv +ww ,X>− 2
≤ (1 + o(1))Ev,w EX∼Q e 2 n
1Γv  ,
{z
}
|
= (I)
where we used that P(Γv |v) = 1 + o(1). Introduce the notation z = |supp(v) ∩ supp(w)|, t+ = |supp(v + w)|,
t− = |supp(v − w)| and t = t+ − t− , so that that z = t+ + t− . Finally, we define the function

r
λ t2+ + t2−
n
√
+
2.1
(t+ + t− ) .
g(t+ , t− ) :=
γ
γ2 n
Under Γv , one has hvv † , Xsupp(v+w) + Xsupp(v−w) i ≤Sg(t+ , t− ). To bound (I), we first integrate with respect
to entries of X outside supp(v + w) × supp(v + w) supp(v − w) × supp(v − w).




λ2 z 2
λ
†
(I) = EX∼Q exp √ hvv , Xsupp(v+w) + Xsupp(v−w) i − 2
1Γv
2γ n
n




λ
λ2 z 2
†
≤ EX∼Q exp √ hvv , Xsupp(v+w) + Xsupp(v−w) i − 2
1hvv† ,Xsupp(v+w) +Xsupp(v−w) i≤g(t+ ,t− )
2γ n
n


2
 q
2 + t2 )
2 2
2(t
λ
(a)
+
−
λ
t
1
g(t
,
t
)γ

+ −
 
√
≤ exp 2 − 
−q

2γ n 2
γ n
2
2
2(t+ + t− )
+

!2 
√
2 2
η t
1 η z 2 + t2
√
 ,
√
≤ exp
−
− 2.1 nγ
2n
2
2 n
+

where we used

2

EY ∼N (0,1) [eaY 1Y ≤b ] ≤ ea

/2−(a−b)2+ /2

and the fact that hvv † , Xsupp(v+w) + Xsupp(v−w) i ∼ N (0, 2(t2+ + t2− )/γ 2 ) in (a) and η = λ/γ in the last
line. When v and w are sampled independently according to the sparse PCA model, then z follows a
hypergeometric distribution with parameters (n, γn, γn). Conditioned on z, t is distributed as a sum of z
independent Rademacher random variables. Returning to the second moment, we arrive at


!2 
√
 02

2 2
2 + t2
P (X)
η
t
1
η
z
√
 .
√
EX∼Q
≤ (1 + o(1)) Ez,t exp
−
− 2.1 nγ
(46)
Q2 (X)
2n
2
2 n
+

0
In comparison to the second
moment
√
√ bound√for the original distribution P(X), the bound for P (X) involves
a correction factor λ z 2 + t2 /2γ n − 2.1 nγ + , which is most effective when z is large. If instead z ≤
n/(2η 2 ), we make use of the bound (33) proved for second moment bound:
 22 


η t
η2
2n
Et e
|z ≤ O 1 +
= O (1) .
(47)
n/z − η 2

20

For larger values of z, we rely on the fact that the hypergeometric distribution with parameters (n, γn, γn)
is stochastically dominated by the Binomial distribution with parameters (γn, γ/(1 − γ)). It follows from
Chernoff’s bound that
 2
ηt
Ez,t e 2n 1z∈(


n
2η 2

,γn/3)

γn/3

(a)



X

≤

exp

z=n/(2η 2 )
γn/3

(b)

X

≤

z=n/(2η 2 )
γn/3

(c)

X

≤

z=n/(2η 2 )
γn/3

(d)

X

≤

z=n/(2η 2 )

η2 z2
− γnhγ/(1−γ)
2n



z
γn



  2


η z
z(1 − γ)
exp z
− log
2n
eγ 2 n
 

  2
1−γ
1
2eλ2
λ
− log
∨
+ log
exp z
6γ
3eγ
4
1−γ
 

  2
1−γ
8e5/4 γ log(1/γ)
λ
− log
∨ log
exp z
6γ
3eγ
1−γ

γn/3

X

≤

exp(−z) = o(1) ,

(48)

z=n/(2η 2 )

where the last line holds for some constant  > 0 in view of (42) and of the condition γ < 1/(81e41 ). We
used in (a) that t ≤ z, in (b) that hp0 (p1 ) ≥ p1 log(p1 /(ep0 )) in (c) that the function x 7→ η 2 x/(2n) − log(x)
is decreasing on (0, 2n/η 2 ] and increasing on [2n/η 2 , ∞). and in (d) that λ2 ≤ −4γ log γ.
Finally, we turn to the case z ∈ [γn/3, γn], for which we will rely on the correcting term in (46). Assume
√
that λ ≥ 9 γ without loss of generality, because otherwise by (43), the second moment is bounded without
any conditioning. For z larger than γn/3,
√

λz
√
√ ≥ 2.1 nγ,
2γ n

and we can once again apply Chernoff’s bound to obtain



!2 
√
2 2
2
2
1 η z +t
η t
√
 1z∈(γn/3,γn] 
√
−
− 2.1 nγ
Ez,t exp
2n
2
2 n
+
"
#

2 !
η2 z2
1
ηz
√
√ − 2.1 nγ
≤ Ez,t exp
−
1z∈(γn/3,γn]
2n
2
2n
+
 2 2
 
γn
X
η z
2.1 √
z
≤
exp
+ √ ηz γ − γnhγ/(1−γ)
4n
γn
2
z=γn/3

(a)

≤

≤

γn
X



η2 z2
2.1 √
z(1 − γ)
exp
+ √ ηz γ − z log
4n
eγ 2 n
2
z=γn/3
  2
 


√
γn
X
2.1η γ
η γ
1
3e
exp z
− log
+ √
+ log
4
γ
1−γ
2


z=γn/3

≤

γn
X

e−z = o(1) ,

z=γn/3

where we used t ≤ z and the fact that the whole exponent is monotone increasing in t2 in the first line. The
last inequality holds for some constant  > 0, because of condition (42) on λ together with the inequality
21

p
λ ≤ 2 γ log(1/γ). In
h 02(a), iwe applied hp0 (p1 ) ≥ p1 log(p1 /(ep0 )). Together with (46), (47), and (48), we
(X)
= O(1).
conclude that EX∼Q PQ2 (X)
Conditional second moment bound for reconstruction In view of (16) and a bounded
√ conditional
second moment, we have DKL (P0 kQ) = O(1). Also, we have kM k∗ = kM k2 = √λn kvk22 = λ n. Therefore,
the conclusion for reconstruction follows by applying Theorem 4 together with Theorem 5.

4.3

Submatrix Localization

√
In this section we prove Theorem 2. Recall that X = (µ/ n) (Y − J/k) + W , where σ0 : [n] → [k] is a
balanced partition, Yi,j = 1σ0 (i)=σ0 (j) , and W is Wigner.
4.3.1

First moment upper bound for submatrix localization

It follows from (14) that the conditional log likelihood ratio reads
log

P(X|σ)
µ
µ2
= √ hY − J/k, Xi −
kY − J/kk2F .
Q(X)
4n
2 n

Therefore, maximizing log P(X|σ)/Q(X) over σ is equivalent to computing
X
Xi,j (Yi,j − 1/k) .
max T (σ) := max
σ

σ

i<j

In both the planted model and the null model, T (σ) is the sum of independent, Gaussian random variables
and is therefore itself Gaussian. Under Q,


n2 (k − 1)
T (σ) ∼ N 0,
+
O(n)
.
2k 2
Under P, denoting by σ0 the planted partition,

 X

µ X
T (σ) = √
1σ0 (i)=σ0 (j) − 1/k 1σ(i)=σ(j) − 1/k +
Wi,j 1σ(i)=σ(j) − 1/k
n i<j
i<j
X

µ X
n2
=√
1σ0 (i)=σ0 (j), σ(i)=σ(j) +
Wi,j 1σ(i)=σ(j) − 1/k − 2 + O(n).
2k
n i<j
i<j
Hence the distribution of T (σ) depends on the overlap matrix ω between σ and the planted partition σ0 .
2
For a given ω, among all n2 pairs i, j with i < j, there are kωkF n2 /2k 2 + O(n) paris such that σ0 (i) = σ0 (j)
and σ(i) = σ(j). Therefore,
!
2
µn2 (kωkF − 1)
n2 (k − 1)
√
T (σ) ∼ N
+ O(n),
+ O(n) .
2k 2
2k 2 n
To prove that detection is possible, notice that in the planted model, maxσ T (σ) ≥ T (σ0 ). Setting ω = I,
Gaussian tail bounds tell us that


p
n2 µ(k − 1)
√
− O(n log n) ≤ n−Ω(1) .
P T (σ0 ) >
2k 2 n
In the null model, taking the union bound over the nk ways to choose σ, we can bound the probability that
any partition is as good, according to T , as the planted one, by


 

p
p
n2 µ(k − 1)
µ2 (k − 1)
√
Q max T (σ) >
+ O( log n/n)
− O(n log n) ≤ exp n log k −
.
σ
4k 2
2k 2 n
22

Thus the probability of this event is e−Ω(n) whenever
µ2 >

4k 2 log k
,
k−1

meaning that above this threshold we can distinguish the null and planted models with generalized likelihood
testing.
To prove that reconstruction is possible, we compute in the planted model the probability that T (σ) >
T (σ0 ) given that σ has L2 overlap z with the planted partition, and argue that this probability tends to zero
whenever the overlap is small enough. Taking the union bound over every σ with L2 overlap at most z gives
#
"

 
p
p
µ2 (k − z)2
n2 µ(k − 1)
√
.
− O(n log n) ≤ exp n log k − 2
+ O( log n/n)
P
max
T (σ) ≥
k (k − 1)
2k 2 n
kω(σ,σ0 )k2F ≤z
By the assumption that µ2 > 4k 2 log k/(k − 1), it follows that there exists a fixed constant  > 0 such that
µ2 (1 − )2 > 4k 2 log k/(k − 1). Hence, setting z = 1 + (k − 1) in the last displayed equation, it yields that
with probability at least 1 − e−Ω(n) ,
max2

T (σ) <

kω(σ,σ0 )kF ≤z

p
n2 µ(k − 1)
√
−
O(n
log n),
2k 2 n

and consequently kw(b
σML , σ0 )k2F ≥ 1 + (k − 1). By Lemma 2, this further implies that the trace overlap satc so that M
cij = (µ/√n)1σb (i)=bσ (j) .
isfies T (b
σML , σ0 ) ≥ 1+(k−1). Moreover, construct an n×n matrix M
ML
ML
ck2 = O(n), and
Then kM
F
2

c, M i = nµ kw(b
hM
σML , σ0 )k2F − 1 + O(1),
2
k
which is at least nµ2 (k − 1)/k 2 + O(1) with high probability. Thus, we can reconstruct the signal matrix
M and the planted partition σ0 better than chance.
4.3.2

Second moment lower bound for submatrix localization

We first prove that when
2

µ <

(
k2

k=2

2k2 log(k−1)
k−1

k ≥ 3,

(49)

then the second moment is bounded. Applying Lemma 1,

EX∼Q

P(X)
Q(X)

2


= Eσ,τ exp


µ2
hY − J/k, Y 0 − J/ki ,
2n

where Yij = 1σ(i)=σ(j) and Yij0 = 1τ (i)=τ (j) . Recall that ω denotes the overlap matrix between partitions σ
and τ . Then hY, Y 0 i = n2 kωk2F /k 2 and hY, Ji = hY 0 , Ji = n2 /k. It follows from the last displayed equation
that

2
 2

P(X)
µ n
2
EX∼Q
= Eσ,τ exp
(kωkF − 1) ,
(50)
Q(X)
2k 2
Lemmata 3, 4 and 5 assure us that this expression is bounded by a constant so long as (49) holds.
For reconstruction, in view of (16) and a bounded second moment, DKL (PkQ) = O(1). Apply Theorem 4
c
c 2
ci] = o(n). Recall that σ0 is the planted
so that for any estimator
O(n), we have E[hM, M
√ M with kM kF = √
partition and M = (µ/ n)(Y − J/k) = (µ/ n)U U † , where U ∈ Rn×k with Uis = 1σ0 (i)=s − 1/k. Then for

23

b such that U
bis = 1σb(i)=s − 1/k and letting M
c = (µ/√n)U
bU
b † , it follows
any estimator σ
b of σ0 , by defining U
that
1
b k2F = 1 EhM, M
ci = o(1).
EkU † U
n2
µ2 n
Finally, notice that by letting ω = ω(b
σ , σ0 ),
b k2F =
kU † U


n2
n2 X
(ω`,s − 1/k)2 = 2 kωk2F − 1 ;
2
k
k
`,s

thus Ekωk2F = 1 + o(1). Hence, we can neither reconstruct the signal matrix M nor the planted partition σ0 .
4.3.3

Conditional second moment lower bound for submatrix localization

Notice that in the large k asymptotic, the right hand side of (49) converges to 2k log k, while the first moment
upper bound gives 4k log k. To match the first moment upper bound in the larger k asymptotic, we apply a
conditional second moment method. In the sequel we assume that
µ2 ≤ 4k log k − 44k log3/4 (k).

(51)

If log k < 114 , then 4k log k − 44k log3/4 k is negative. Hence, we focus on the setting log k ≥ 114 .
For any partition σ : [n] → k, let M = √µn (Yσ − J/k) and define the event Γσ by


p
Γσ := sup [X − M ]σ−1 (`) ≤ 3 n/k ,
2

1≤`≤k

where [X − M ]σ−1 (`) denotes the σ −1 (`) × σ −1 (`) submatrix of X − M . In other words, on Γσ , the specp
tral noms of submatrices [X − M ]σ−1 (`) for every 1 ≤ ` ≤ k are all upper bounded by 3 n/k. Since
[X − M ]σ−1 (`) is distributed as a Wigner Matrix under P(.|σ), by Gaussian concentration theorem and
Slepian’s inequality we have
h
i
p
2
P [X − M ]σ−1 (`) ≥ 2 n/k + t | σ ≤ e−t /4 , ∀1 ≤ ` ≤ k.
2

Since k = o(n/ log(n)), we have P(Γσ |σ) = 1 + o(1) uniformly with respect to σ.
Next, we condition on the high probability events Γσ by defining


1Γσ
,
P0 (X) = Eσ P(X|σ)
P(Γσ |σ)
It follows that the conditional second moment satisfies
"
2 #



P0 (X)
P(X|σ)P(X|τ )
1Γσ 1Γτ
EX∼Q
= Eσ,τ EX∼Q
Q(X)
Q2 (X)
P(Γσ |σ)P(Γτ |τ )




µ
µ2
2
√ hX,Yσ +Yτ −2J/ki−
2n kYσ −J/kkF
1Γσ  ,
= (1 + o(1))Eσ,τ EX∼Q e 2 n
|
{z
}
= (I)
where we used that P(Γv |v) = 1 + o(1). Given σ and τ , define A``0 = σ −1 (`) ∩ τ −1 (`0 ) and the event




 X

p
µ
1
Γ``0 =
|A``0 |2 + 3|A``0 | n/k
Xij ≤ √
1−


k
n
i,j∈A``0

24

Obviously, Γ``0 ⊂ Γσ for all `, `0 ∈ [k]. Equipped with this notation, we bound (I) by the exponential moment
of k 2 + 1 thresholded normal random variables:


 Y

k
2
µ
µ
√ hX, Yσ + Yτ − 2J/ki −
kYσ − J/kk2F
1Γ``0 
(I) ≤ EX∼Q exp
2n
2 n
`,`0 =1
r 2 !
 2
 Y
 

k
n
µ
1 |A``0 |
1
√
−3
≤ exp
hYσ − J/k, Yτ − J/ki
exp − µ 1 −
2n
2
k
2k
2n
+
0
`,` =1

where we used

2

EZ∼N (0,1) [eaZ 1Z≤b ] ≤ ea

/2−(a−b)2+ /2

.

Recall that ω denotes the overlap matrix between σ and τ . Then hYσ , Yτ i = nkωk2F /k 2 , hYσ , Ji = hYσ , Ji =
n2 /k and |A``0 | = nω``0 /k. Define
ak :=3 log1/4 (k)
bk :=2/k + 6/ak .
It follows from the last displayed equation that
log(I)
n

≤
≤

√ !2
k
1
1− −3
k
µω``0
`,`
+


2
2 X
µ
µ
1
2
(1 + bk )(kωk2F − 1) + 2
ω``
1ω 0 ≤√kak /µ ,
0 −
2
``
4k 2
4k
k
0
µ2
µ2 X 2
2
(kωk
−
1)
−
ω 0
F
2k 2
4k 2 0 ``

(52)

`,`

where we used (1 − x)2+ ≥ max((1 − 2x), 0) and bk ≤ 1 since log k ≥ 114 in the second line. Unfortunately,
the expression



X
1
2
exp 
1ω 0 ≤√kak /µ 
ω``
0 −
``
k2
0
`,`

is not easy to integrate over ω. This is why we shall bound it by a combination of the entropy of ω and a
second degree polynomial.
Lemma 7. Let t ∈ (0, 1) be such that t ≤ 0.4 and t ≥ k3 ∨ ( ke )1/5 ∨
2+5t
ct := log5tk−1 − k[log
k−1] > 0, we have for any x ∈ [0, 1],

1−1/k
2[log k−1]

∨

2 log k
5(k−2 log k+1) .



1
1
log k
)1
≤
5t(x
−
)(1
−
x)
+
c
x
log(x)
+
.
x<t
t
k2
k
k
h
i
Proof. Indeed, let g be defined by g(x) = 5t(x − k1 )(1 − x) + ct x log(x) + logk k − (x2 −

Upon defining

(x2 −

0

00

ct
x

(53)
1
k2 )1x<t .

For any

x 6= t, g (x) = 5t(−2x + 1 + 1/k) + ct log(xe) − 2x1x<t and g (x) = − 10t − 2 · 1x<t . Since ct ≤ 10t2 , g 0 is
increasing on (0, ct /[2 + 10t]) and decreasing on (ct /[2 + 10t], t) and (t, 1]. Besides, ct /[2 + 10t] ≥ 1/k as this
2 log k
0
inequality reduces t ≥ 5(k−2
log k+1) . Since ct has been chosen in such a way that g (1/k) = 0, the minimum
of g is either achieved at 1/k, t− , or 1. We have g(1/k) = 0 and g(1) = ct log k/k > 0, and
g(t− ) ≥ 5t(t − 1/k)(1 − t) − ct t log(1/t) − t2 ≥ t2 −

5t2 log(1/t)
≥0,
log k − 1

where we used (t − 1/k)(1 − t) ≥ 2t/5 and t ≥ (e/k)1/5 . We have proved (53).

25

√
√
√
Since µ ≤ 2 k log k, we have kak /µ ≥ 32 log−1/4 (k). Assuming that µ ≥ 2.5 kak and since log k ≥ 114 ,
√
the assumptions of (53) are satisfied for t = kak /µ. Writing ck for c√kak /µ , it follows from (52) and (53)
that




5µak X
log(I)
µ2
1
µ2 ck X
log k
2
0 −
0) +
0 log(ω``0 ) +
(1
+
b
)(kωk
−
1)
+
≤
ω
(1
−
ω
ω
k
``
``
``
F
n
4k 2
k
4k 2
k
4k 3/2 0
0
`,`

(a)

≤
≤
≤

2

`,`

2

µ
(1 + bk )(kωk2F − 1) −
4k 2
µ2
(1 + bk )(kωk2F − 1) −
4k 2

µ ck
[H(ω) − log k]
4k
5µak
√
[H(ω) − log k]
4 k(log k − 1)

µ2
(1 + bk )(kωk2F − 1) −
4k 2

15
2

log−1/4 (k) [H(ω) − log k] ,

P
where (a) follows because ω is doubly stochastic so that `,`0 (ω``0 − k1 )(1 − ω``0 ) = 1 − kωk2F ≤ 0; the
√
√
last inequality holds due to µ ≤ 2 k log k. If µ ≤ 2.5 kak , we simply come back to (52) to ensure that
2
µ
2
log(I) ≤ n 2k
2 (kωkF − 1). We arrive at
"
2 #


P0 (X)
EX∼Q
≤ (1 + o(1))Eσ,τ exp n t1 (kωk2F − 1) − t2 (H(ω) − log k)
(54)
Q(X)
√
√
−1/4
µ2
µ2
kak and t1 = 4k
with t1 = 2k
(k) when µ ≥ 2.5 kak .
2 and t2 = 0 when µ < 2.5
2 (1 + bk ) and t2 = 8 log
Hence, to prove the conditional second moment is bounded, it reduces to verifying the right hand side of
(54) is bounded. By assumption (51) and log k ≥ 114 , it holds that


4k 2
µ2 ≤
log(k − 1) − 8 log(k − 1) log−1/4 (k) − 1 .
(k − 1)(1 + bk )
This further implies that
t1
log(k − 1) − 1/(1 − t2 )
≤
.
1 − t2
k−1
Therefore, by Lemma 4, we have that for all ω,

1
(H(ω) − log k) (1 − t2 ) + t1 kωk2F − 1 ≤ −
(kωk2F − 1).
k−1
Hence, assumptions in Lemma 3 are satisfied with ϕ(ω) = t1 (kωk2F − 1) − t2 [H(ω) − log k] and δ = 1/(k − 1),
and it follows from Lemma 3 that the right hand side of (54) is bounded.
Conditional second moment bound for reconstruction In view of (16) and a bounded conditional
second moment, we have DKL (P0 kQ) = O(1). Also, we have that
√
µ
µ
kM k2 = √ kY − J/kk2 ≤ √ (kY k2 + kJk2 /k) = 2µ n/k
n
n
√
and since M is of rank k, kM k∗ ≤ kkM k2 ≤ 2µ n. Therefore, the conclusion for reconstruction follows by
applying Theorem 4 together with Theorem 5.

4.4

Gaussian Mixture Clustering

Finally, we turn to the Gaussian Mixture Clustering problem, where σ : [n] → [k] is a balanced partition
i.i.d.

chosen uniformly at random, v1 , . . . , vk ∼ N (0, k/(k − 1)In,n ), and we observe the matrix
r 

ρ
1
X=
S − Jm,k V † + W,
n
k
26

(55)

where W has independent standard normal entries, S is an m × k matrix with Si,t = 1σ(i)=t , and V =
[v1 , . . . , vk ].
4.4.1

First moment upper bound for Gaussian mixture clustering

In this section, we derive an upper bound on the detection and reconstruction threshold via the first moment
method. The testing procedure is again based on the generalized likelihood ratio supv,σ log P(X|v, σ)/Q(X),
which from (14) we write as
r
ρ
ρ
P(X | v, σ)
2
(S − Jm,k /k)V † F
=
hX, (S − Jm,k /k)V † i −
log
Q(X)
n
2n
r
k
k
ρX X
ρm X
=
h
xi , vs − vi −
kv` − vk22 .
n s=1
2nk s=1
i:σ(i)=s

When σ is fixed, we can optimize in v by setting the sth cluster center to
√
k n X
xi ,
vs − v = √
m ρ
i:σ(i)=s

the rescaled center of the data points xi which have been assigned to cluster s according to σ. Up to
multiplicative constants, then, the generalized likelihood ratio test is equivalent to the test based on the
statistic
2

k X
max T (σ) := max
σ
σ m
s

X

xi

.

(56)

σ(i)=s

In the null model, for any fixed σ,
T (σ) ∼ χ2nk ,
where χ2nk is the central chi-squared distribution with nk degrees of freedom.
In the planted model, let v 0 and σ0 denote the planted vectors and partition respectively, and for an
arbitrary partition σ, let ω once again be the overlap matrix between σ and σ0 . For any 1 ≤ ` ≤ k,
!
√
X
m ρX
m
√
ωs,t (vt0 − v 0 ), I .
xi ∼ N
k
k n t
σ(i)=s

For y ∼ N (µ, Id ), let χ2d (kµk2 ) denote the distribution of kyk2 , which is known as non-central chi-square
distribution with d degrees of freedom and non-centrality kµk2 . In this notation, T (σ) is distributed in P as
a non-central chi-squared random variable with nk degrees of freedom and noncentrality
k
αρ X X
ω`,s (vs0 − v 0 )
k
s
`=1

2

k

αρ X X
ω`,s ω`,t hvs0 − v 0 , vt0 − v 0 i
k
`=1 s,t

p
nαρ 
2
=
kωkF − 1 + O( n log n).
k−1
=

(57)

To obtain the last line, note that the v`0 are Gaussian
√ with zero mean and variance k/(k − 1)√in each
coordinate, making hvs0 − v 0 , vt0 − v 0 i = −n/(k − 1) + O( n log n) for s 6= t and kvs0 − v 0 k2 = n + O( n log n)
with high probability.

27

We will need the following tail bounds for non-central chi-squared distributions [13, Lemma 8.1]: for
t > 0,
#
"
r



2
2
2
2
d + 2 kµk t < e−t
(58)
Pr χd kµk < d + kµk − 2
"



2

Pr χ2d kµk



2

> d + kµk + 2

r

2

d + 2 kµk



#
t + 2t < e−t

(59)

2

Notice that we can obtain central chi-square tail bounds by setting kµk = 0.
To derive the first moment bound for detectability, notice that in the planted model, when σ = σ0 up to
2
a permutation of cluster indices, kωkF = k and


p
T (σ0 ) ∼ χ2nk αnρ + O( n log n) .
√
Setting t = log n in (58), we know that with high probability T (σ0 ) > nk + nαρ − O( n log n).
In the null model, by the union bound and (59), letting t = (1+)m log k for an arbitrarily small constant
 > 0,
i
h
i
h
√
√
Q max T (σ) > nk + 2 nkt + 2t = k m Pr χ2nk > nk + 2 nkt + 2t = e−Ω(m) ,
σ

Hence, with high probability, in the null model,
p
max T (σ) ≤ nk + 2 (1 + )mnk log k + 2(1 + )m log k.
σ

√
√
√
By the assumption that ρ > ρupper , i.e., ρ α > 2 k log k + 2 α log k, it follows that for sufficiently large n,
p

p

nαρ − O
n log n ≥ 2(1 + )
mnk log k + m log k ,
√
and consequently,
√ with high probability, maxσ T (σ) > nk + nαρ − O( n log n) under P, and maxσ T (σ) <
nk + nαρ − O( n log n) under Q.
To show reconstruction is possible above this bound, let σ have overlap matrix ω with σ0 and set
kωk2F = θ. We will show that, when θ is sufficiently small, there are with high probability no such partition
with likelihood as high as the planted one. In the planted model,


p
θ−1
T (σ) ∼ χ2nk nαρ
+ O( n log n) .
k−1
Taking the union bound over all partitions σ which have L2 overlap at most 1 + (k − 1) with the planted
one—of which there are no more than k m —and invoking (59) with t = (1 + )m log k, we know that with
high probability,
p
max
T
(σ)
≤
nk
+
nαρ
+
2
(1 + ) (nk + 2nαρ) m log k
2
σ:kω(σ,σ0 )kF ≤1+(k−1)

p
+ 2(1 + )m log k + O( n log n),
√
√
√
By the assumption that ρ α > 2 k log k + 2 α log k, it follows that for sufficiently large n,
p

p

nαρ(1 − ) − O
n log n ≥ 2(1 + )
(nk + 2nαρ)m log k + m log k ,
and consequently, with high probability,
max

σ:kω(σ,σ0 )k2F ≤1+(k−1)

28

T (σ) < T (σ0 ).

Let σ
bML = arg max T (σ) denote the maximum likelihood estimator of σ0 . Then with high probability,
2
kω(b
σML , σ0 )kF ≥ 1 + (k − 1), which further implies that the trace overlap satisfies T (b
σML , σ0 ) ≥ 1 + (k − 1)
in view of Lemma 2.
c of M such that
Finally, we argue that above the first moment bound, one can construct an estimator M
ck2 ] = O(n2 ) and E[hM, M
ci] = Ω(n). Intuitively, if we can estimate the planted partition better than
E[kM
F
chance, then we should be able to construct an estimator of the signal matrix which out-performs the trivial
one. Our proof uses the sample splitting method. Thinking of the rows of X as noisy observations of the
cluster centers contained in the rows of M , we will project each observation into two orthogonal subspaces,
use the first of these projections to build an estimator σ
b of the planted partition σ0 , and finally combine σ
b
with the second projection to estimate the cluster centers. This technique gains us a subtle and important
independence property: the partition we estimate based on the first projection is independent of the noise
in the second.
Let us proceed. For δ ∈ (0, 1) to be optimized later, let n1 = (1−δ)n ∈ N and denote by X1 ∈ Rm×n1 and
X2 ∈ Rm×(n−n1 ) the restrictions of the data matrix X to its first n1 and final n − n1 columns respectively;
0
define M1 and M2 analogously. We first reconstruct M1 from
√ parameters
√ ρ = (ρ/n)n1 = (1 − δ)ρ
√ X1 with
0
and α = m/n1 = α/(1 − δ). Notice that
ρ√ α > 2 k log k + 2 α log k means that we can
√ our assumption
√
choose δ sufficiently small to ensure ρ0 α0 > 2 k log k + 2 α0 log k. Let σ
b denote the ML estimator of the
2
planted partition based only on the data X1 . We have already shown that kω(b
σ , σ0 )kF ≥ 1 + (k − 1) with
high probability.
Now we use σ
b to construct an estimator of M2 . Specifically, let Sb be the m × k indicator matrix for σ
b,
b
c2 = (k/m)SbSb† X2 . Then
Sis = 1σb(i)=s , and define M
k
k
c2 i = k EhM2 , SbSb† (M2 + W2 )i (a)
EhM2 , M
=
EhM2 , SbSb† M2 i = EkSb† M2 k2F ,
m
m
m
where (a) follows because the noise W2 is independent of M2 and Sb and EW2 = 0. Furthermore,
k
k
k m2 ρ X X
EkSb† M2 k2F =
ω`,s (u0s − ū0 )
m
m k2 n
s

2

,

`=1

where u0s is the restriction of vs0 to the last δn coordinates, ū0 is the restriction of v̄ 0 to the last δn coordinates,
c2 i = Ω(n).
and ω`,s = ω(b
σ , σ0 ). In view of (57), it follows from the last two displayed equations that EhM2 , M
2
2
c
c
c
One can additionally verify that that EkM2 kF = O(n ). Finally letting M = [0m,n1 , M2 ] be the estimator,
c2 on the left with n1 zero columns, we have shown that EkM
ck2 = O(n2 ) and EhM, M
ci =
i.e., concatenating M
F
Ω(n).
4.4.2

Second moment lower bound for Gaussian mixture clustering

We first show that if ρ < ρlower , i.e., αρ2 < 2(k − 1) log(k − 1), then the second moment is bounded. Recall
that S is the m × k indicator matrix for a partition σ with Si,t = 1σ(i)=t , and V = [v1 , . . . , vk ]. Let τ be an
independent copy of σ, with indicator matrix Ti,t = 1τ (i)=t and U = [u1 , . . . , uk ] be an independent copy of
V . Applying Lemma 1,

EX∼Q

P(X)
Q(X)

2

ρ

(S − Jm,k /k)V † , (T − Jm,k /k)U †
n
 αρ

= Eσ,τ Ev,u exp
hU, V (ω − J/k)i ,
k

= Eσ,τ Ev,u exp



where ω is the overlap matrix between σ and τ . The last equality follows from S † T = (m/k)ω and S † Jm,k =
p
e analogously, so that these two matrices now
(m/k)Jk,k = J†m,k T . Let Ve = (k − 1)/k V and define U
contain i.i.d standard Gaussian entries. Evaluating the moment generating function for the Gaussian random

29

e and invoking the standard linear algebra result that kABkF ≤ kAk2 kBkF , it follows that
matrix U


 αρ

αρ e e
Ev,u exp
hU, V (ω − J/k) = Ev,u exp
hU , V (ω − J/k)i
k
k−1


2
α2 ρ2
e
V (ω − J/k)
= Ev exp
2(k − 1)2
F


α2 ρ2
2
2
e
≤ Ev exp
kV k2 k(ω − J/k)kF .
2(k − 1)2
In view of [48, Corollary 5.35], Ve is a ‘tall’ Gaussian random matrix with spectral norm tightly concentrated:
h
i
√
√
2
Pr kVe k2 ≤ n + k +  ≤ e− /2 .
p
Since k is assumed to be fixed constant, with high probability kVe k2 ≤ (1 + )n for an arbitrarily small
constant  > 0. Notice that if this event does not hold, the second moment becomes unbounded. We therefore
will compute the second moment conditioned on the high probability event that kVe k is not abnormally large.
As we discussed in §3.2, we define the event
p
F = {V : kVe k2 ≤ (1 + )n},
and conditional distributions P0 (v, σ) = P(v, σ)1F /P(F) and P0 (X) = Ev,σ∼P0 [P(X|v, σ)]. Notice that
P {F} → 1. Then the conditional second moment satisfies
2
 0
 αρ

1
P (X)
EX∼Q
≤ 2
Eσ,τ Ev,u exp
hU, V (ω − J/k) 1U ∈F 1V ∈F
Q(X)
P (F)
k
 αρ

1
Eσ,τ Ev,u exp
hU, V (ω − J/k) 1V ∈F
≤ 2
P (F)
k


1
α2 ρ2
2
2
e
Eσ,τ Ev exp
kV k2 k(ω − J/k)kF 1V ∈F
≤ 2
P (F)
2(k − 1)2


α 2 ρ2 n
1
2
Eσ,τ exp (1 + )
kω − J/k)kF .
≤ 2
P (F)
2(k − 1)2
As in the submatrix localization problem, it remains to show that


α 2 ρ2 n
2
Eσ,τ exp (1 + )
kω
−
J/k)k
F
2(k − 1)2

(60)

is bounded by a constant for a sufficiently small . This is guaranteed if αρ2 < 1 for k = 2 and αρ2 <
2(k − 1) log(k − 1) for k > 2, in view of Lemmata 3, 4 and 5.
For reconstruction, notice that the conditioned planted model P0 is still an additive Gaussian model. Let
P (M |X) denote the posterior distribution of M given X under P0 , i.e., P0 (M |X) = P(X|M )P0 (M )/P0 (X).
Let E 0 (X) = EM ∼P0 (M |X) [M ] denote the posterior mean under P0 . Applying Theorem 4 with P0 and Q, we
obtain
h
i
1
1
1
2
2
2
EM ∼P kM kF 1F ,
lim EM,X∼P0 kM − E 0 (X)kF = lim EM ∼P0 kM kF = lim
n→∞ n
n→∞ nP(F)
n→∞ n
0

where the last equality follows from the definition of P0 . Let E(X) = EM ∼P(M |X) [M ] denote the posterior
mean under P. Then
2

2

EM,X∼P0 kM − E 0 (X)kF ≤ EM,X∼P0 kM − E(X)kF
h
i
1
2
=
EM,X∼P kM − E(X)kF 1F
P(F)
1
2
≤
EM,X∼P kM − E(X)kF ,
P(F)
30

where the first inequality holds because E 0 (X) minimizes the mean squared error under P0 ; the second
equality holds by the definition of P0 . Combining the last two displayed equations yields that
h
i
1
1
2
2
lim inf EM,X∼P kM − E(X)kF ≥ lim EM ∼P kM kF 1F .
(61)
n→∞ n
n→∞ n
Since
ρ
ρ
kM kF = k(S − Jm,k /k)V kF ≤ kS − Jm,k kF kV kF = O(kV kF ),
n
n
it follows that
i
h

4
EM ∼P kM kF = O EV [kV k4F ] = O(n2 ).
Hence,
h

2
EM ∼P kM kF

i

r

1F c ≤

!
r
h
i
h
i
4
4
c
EM ∼P kM kF P(F ) = o
EM ∼P kM kF
= o(n).

Combing the last displayed equation with (61) gives that
lim inf
n→∞

h
i
1
1
2
2
EM,X∼P kM − E(X)kF ≥ lim EM ∼P kM kF .
n→∞ n
n
2

2

Since E(X) minimizes the mean squared error under P, EM,X∼P kM − E(X)kF ≤ EM ∼P kM kF , it follows
that
i
h
1
1
2
2
lim EM,X∼P kM − E(X)kF = lim EM ∼P kM kF ,
n→∞ n
n→∞ n
2
c
and thus limn→∞ (1/n)EX∼P kE(X)kF = 0. By (21) in Theorem 4, we conclude that for any estimator M
2
c
c
with kM kF = O(n), E[hM, M i] = o(n).

4.5

Proof of Theorem 4

We give the proof for i.i.d. Gaussian noise, using a type of interpolation argument
where we vary the signal
√
to noise ratio; the proof for Wigner noise is identical. Assume that X(β) = βM + W in the planted model
and X = W in the null model, where β ∈ [0, 1] is a signal-to-noise ratio parameter (analogous to an inverse
i.i.d.

temperature) and Wij ∼ N (0, 1) for all i, j.
First recall that the Bayes-optimal estimator minimizing the mean squared error is the expectation of
the posterior distribution,
cMMSE (X) = E[M |X] ,
M
so that the (rescaled) minimum mean squared error is given by
MMSE(β) =

1
EkM − E[M |X] k2F .
n

(62)

c = 0,
We will start by proving that, for all β ∈ [0, 1], the MMSE tends to that of the trivial estimator M
lim sup MMSE(β) = β lim

n→∞

n→∞

1
EkM k2F .
n

(63)

Let us compute the mutual information I(β) between M and X:
P(X|M )
P(X)
Q(X)
P(X|M )
= EX log
+ EM,X log
P(X)
Q(X)


p
βkM k2F
= −DKL (PkQ) + EM,X
βhM, Xi −
2
β
= −DKL (PkQ) + EM kM k2F .
2

I(β) = EM,X log

31

(64)

By assumption, we have DKL (PkQ) = o(n). This holds for β = 1; by the data processing inequality for KL
divergence [45, Theorem 2.2], this holds for all β < 1 as well. Thus (64) becomes
lim

n→∞

β
1
1
I(β) =
lim E kM k2F .
n
2 n→∞ n

(65)

Next we compute the MMSE. Recall the I-MMSE formula [22],
dI(β)
n
= MMSE(β) ,
dβ
2

(66)

which can also be viewed as a classic formula in thermodynamics. Note that the MMSE is by definition
c = 0, so that for all β we have
bounded above by the squared error of the trivial estimator M
MMSE(β) ≤

1
E kM k2F .
n

(67)

Combining these we have
 (a)
1 
1
1
lim
E kM k2F = lim I(1)
n→∞ n
2 n→∞ n
Z 1
(b) 1
lim
MMSE(β) dβ
=
2 n→∞ 0
Z 1
(c) 1
≤
lim sup MMSE(β) dβ
2 0 n→∞
Z
1
(d) 1
1
E kM k2F dt
≤
lim
2 0 n→∞ n
1
1
=
lim
E kM k2F ,
2 n→∞ n
where (a) and (b) hold due to (65) and (66), (c) follows from the Fatou lemma, and (d) follows from (67).
Since we began and ended with the same expression, these inequalities must all be equalities. In particular,
since (c) holds with equality, we have
lim sup MMSE(β) = lim

n→∞

n→∞

1
E kM k2F
n

(68)

for almost all β ∈ [0, 1]. Since MMSE(β) is a non-increasing function of β, its limit lim supn→∞ MMSE(β) is
also non-increasing in β. Therefore, (68) holds for all β ∈ [0, 1]. This completes the proof of our claim that
the optimal estimator has the same asymptotic MMSE as the trivial one.
To show that the optimal estimator actually converges to the trivial one, we expand the definition of
MMSE(β) in (62) and subtract (68) from it. This gives
lim sup
n→∞


1 
E −2hM, E[M |X]i + kE[M |X] k2F = 0 .
n

(69)

Note that EhM, E[M |X]i is the expected inner product between the ground truth and a draw from the
posterior. By the Nishimori identity [25] or the tower property of conditional expectation, this is equal to
the expected inner product between two independent draws from the posterior. By linearity of the inner
product, this gives
E hM, E[M |X]i = E hE[M |X] , E[M |X]i = E kE[M |X] k2F ,
and combining this with (69) gives (where lim sup becomes lim inf because of a sign change)
lim inf
n→∞

1
E kE[M |X] k2F = 0 .
n
32

(70)

c=M
c(X) such that EX kM
ck2 = O(n),
Furthermore, for any estimator M
F
h
i q
c
c
c
ck2 ]
EM,X hM, M i = EX hE[M |X] , M i ≤ EX kE[M |X] kF kM kF ≤ EX [kE[M |X] k2F ] EX [kM
F
and thus the desired (21) holds.
√
Finally, we note that if M is of the form (1/ n)U V † where the rows of U and V are independently and
identically distributed according to some priors, then limn→∞ MMSE(β) exists by [20, Proposition III.2],
cMMSE = E[M |X] tends
and the liminf in (20) and (21) can be replaced by lim. Then the MMSE estimator M
c = 0 as claimed.
to the trivial estimator M

4.6

Proof of Theorem 5

We give the proof of i.i.d. Gaussian noise; the proof for Wigner noise is identical. Let
Z(X) :=

h
i
2
P(X)
= EM ehM,Xi−kM kF /2 .
Q(X)

By the definition of KL divergence,
DKL (P0 kQ) − DKL (PkQ)




P(X)
P0 (X)
0
− EX∼P log
= EX∼P log
Q(X)
Q(X)






0
P (X)
P(X)
P(X)
0
0
= EX∼P log
+ EX∼P log
− EX∼P log
P(X)
Q(X)
Q(X)
≥ EX∼P0 [log Z(X)] − EX∼P [log Z(X)] ,
where the last inequality follows because DKL (P0 kP) = EX∼P0 [log(P0 (X)/P(X))] ≥ 0. Furthermore,
EX∼P0 [log Z(X)] − EX∼P [log Z(X)]
1
= EPM
EP(X|M ) [(1FM − P(FM |M )) log Z(X)]
P(FM |M )
q


1
≥ −EPM
P(FM |M ) (1 − P(FM |M )) EP(X|M ) log2 Z(X)
P(FM |M )
q


= −o(1) × EPM EP(X|M ) log2 Z(X) ,
where we use the Cauchy-Schwarz inequality in the third line, and the assumption that P(FM |M ) = 1 + o(1)
uniformly over M in the last line.
√
√
By the assumptions that kM k2 = O( n) and kM k∗ = O( n) uniformly√over all M , and in view of
hM, Xi ≤ kM k∗ kXk2 and kM k2F ≤ kM k∗ kM k2 , we have that | log Z(X)| ≤ O ( nkXk2 ) + O(n). Therefore,






EP(X|M ) log2 Z(X) = O(n2 ) + O(n) × EP(X|M ) kXk22 = O(n2 ) + O(n) × EW kM + W k22 = O(n2 ),






where the last inequality holds because EW kM + W k22 ≤ 2kM k22 + 2EW kW k22 and EW kW k22 = O(n).
Combining the last three displayed equations together yields that
DKL (P0 kQ) − DKL (PkQ) ≥ EX∼P0 [log Z(X)] − EX∼P [log Z(X)] ≥ −o(n).

Acknowledgments
We thank Yihong Wu, Lenka Zdeborová, Florent Krzakala, Thibault Lesieur, Caterina de Bacco, Alex
Russell, Andrea Montanari, and Cosma Shalizi for helpful discussions. C. Moore and J. Banks are supported
33

by the John Templeton Foundation and the ARO under contract W911NF-12-R-0012. J. Xu is supported
by Simons-Berkeley Research Fellowship. R. Vershynin is suppored by NSF Grant DMS 1265782 and U.S.
Air Force Grant FA9550-14-1-0009. Much of this work was done while the authors were visiting the Simons
Institute for the Theory of Computing.

References
[1] E. Abbe and C. Sandon. Detection in the stochastic block model with multiple clusters: proof of the
achievability conjectures, acyclic bp, and the information-computation gap. arXiv 1512.09080, Dec 2015.
[2] D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In Learning Theory,
pages 458–469. Springer, 2005.
[3] D. Achlioptas and A. Naor. The two possible values of the chromatic number of a random graph. Annals
of Mathematics, 162:1335–1351, 2005.
[4] D. J. Aldous. Exchangeability and related topics. In École d’été de probabilités de Saint-Flour, XIII—
1983, volume 1117 of Lecture Notes in Math., pages 1–198. Springer, Berlin, 1985.
[5] A. A. Amini and M. J. Wainwright. High-dimensional analysis of semidefinite relaxations for sparse
principal components. Ann. Statist., 37(5B):2877–2921, 10 2009.
[6] E. Arias-Castro and N. Verzelen. Community detection in dense random networks. Ann. Statist.,
42(3):940–969, 06 2014.
[7] Z. Bai and J. W. Silverstein. Spectral analysis of large dimensional random matrices. Springer Series
in Statistics. Springer, New York, second edition, 2010.
[8] J. Baik, G. Ben Arous, and S. Péché. Phase transition of the largest eigenvalue for nonnull complex
sample covariance matrices. Annals of Probability, pages 1643–1697, 2005.
[9] J. Banks, C. Moore, J. Neeman, and P. Netrapalli. Information-theoretic thresholds for community
detection in sparse networks. In Proceedings of the 29th Conference on Learning Theory, COLT 2016,
New York, NY, June 23-26 2016, pages 383–416, 2016.
[10] J. Banks, C. Moore, R. Vershynin, and J. Xu. Information-theoretic bounds and phase transitions in
clustering, sparse PCA, and submatrix localization. arXiv:1607.05222, 2016.
[11] F. Benaych-Georges and R. R. Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227(1):494–521, 2011.
[12] Q. Berthet, P. Rigollet, et al. Optimal detection of sparse principal components in high dimension. The
Annals of Statistics, 41(4):1780–1815, 2013.
[13] L. Birgé. An alternative point of view on Lepski’s method. State of the art in probability and statistics,
pages 113–133, 2001.
[14] C. Bordenave, M. Lelarge, and L. Massoulié. Non-backtracking spectrum of random graphs: Community
detection and non-regular ramanujan graphs. In IEEE 56th Annual Symposium on Foundations of
Computer Science, FOCS, pages 1347–1357, 2015.
[15] C. Butucea and Y. I. Ingster. Detection of a sparse submatrix of a high-dimensional noisy matrix.
Bernoulli, 19(5B):2652–2688, 11 2013.
[16] T. Cai, Z. Ma, and Y. Wu. Optimal estimation and rank detection for sparse spiked covariance matrices.
Probability Theory and Related Fields, 161(3):781–815, 2015.
34

[17] Y. Chen and J. Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. In Proceedings of ICML 2014 (Also
arXiv:1402.1267), Feb 2014.
[18] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model
for modular networks and its algorithmic applications. Physics Review E, 84:066106, 2011.
[19] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Inference and phase transitions in the detection
of modules in sparse networks. Physical Review Letters, 107(6):065701, 2011.
[20] Y. Deshpande and A. Montanari. Information-theoretically optimal sparse PCA. In Information Theory
(ISIT), 2014 IEEE International Symposium on, pages 2197–2201, June 2014.
[21] Y. Deshpande and A. Montanari. Sparse PCA via covariance thresholding. In Advances in Neural
Information Processing Systems, pages 334–342, 2014.
[22] D. Guo, S. Shamai, and S. Verdú. Mutual information and minimum mean-square error in gaussian
channels. IEEE Trans. on Information Theory, 51, 2005.
[23] B. Hajek, Y. Wu, and J. Xu. Information limits for recovering a hidden community. arXiv 1509.07859,
September 2015.
[24] B. Hajek, Y. Wu, and J. Xu. Submatrix localization via message passing. arXiv 1510.09219, October
2015.
[25] Y. Iba. The nishimori line and bayesian statistics. Journal of Physics A: Mathematical and General,
32(21):3875, 1999.
[26] Y. I. Ingster and I. A. Suslina. Nonparametric goodness-of-fit testing under Gaussian models. Springer,
New York, NY, 2003.
[27] E. S. P. J. Neyman. On the problem of the most efficient tests of statistical hypotheses. Philosophical
Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical
Character, 231:289–337, 1933.
[28] I. M. Johnstone and A. Y. Lu. On consistency and sparsity for principal components analysis in high
dimensions. Journal of the American Statistical Association, 104(486):682–693, June 2009.
[29] R. Kannan, H. Salmasian, and S. Vempala. The spectral method for general mixture models. SIAM
Journal on Computing, 38(3):1141–1156, 2008.
[30] R. Kannan and S. Vempala. Spectral algorithms. http://www.cc.gatech.edu/ vempala/spectralbook.pdf,
2009.
[31] M. Kolar, S. Balakrishnan, A. Rinaldo, and A. Singh. Minimax localization of structural information
in large noisy matrices. In Advances in Neural Information Processing Systems, 2011.
[32] R. Krauthgamer, B. Nadler, and D. Vilenchik. Do semidefinite relaxations solve sparse PCA up to the
information limit? The Annals of Statistics, 43(3):1300–1322, June 2015.
[33] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption
in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940,
2013.
[34] F. Krzakala, J. Xu, and L. Zdeborová. Mutual information in rank-one matrix estimation. arXiv
1603.08447, March 2016.

35

[35] M. Lelarge and L. Miolane.
arXiv:1611.03888, Nov. 2016.

Fundamental limits of symmetric low-rank matrix estimation.

[36] T. Lesieur, C. D. Bacco, J. Banks, F. Krzakala, C. Moore, and L. Zdeborová. Phase transitions and
optimal algorithms in high-dimensional gaussian mixture clustering. Arxiv preprint arxiv:1610.02918,
2016.
[37] T. Lesieur, F. Krzakala, and L. Zdeborová. MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel. In 2015 53rd Annual Allerton Conference on Communication,
Control, and Computing (Allerton), pages 680–687, Sept 2015.
[38] T. Lesieur, F. Krzakala, and L. Zdeborová. Phase transitions in sparse PCA. In 2015 IEEE International
Symposium on Information Theory (ISIT), pages 1635–1639. IEEE, 2015.
[39] E. Mossel, J. Neeman, and A. Sly. Belief propagation, robust reconstruction and optimal recovery of
block models. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona,
Spain, June 13-15, 2014, pages 356–370, 2014.
[40] E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model.
Probability Theory and Related Fields, 162(3-4):431–461, 2015.
[41] D. Paul. Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statistica
Sinica, 17(4):1617–1642, 2007.
[42] S. Péché. The largest eigenvalue of small rank perturbations of hermitian random matrices. Probability
Theory and Related Fields, 134(1):127–173, 2006.
[43] A. Perry, A. S. Wein, and A. S. Bandeira. Statistical limits of spiked tensor models. arXiv:1612.07728,
Dec. 2016.
[44] A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra. Optimality and sub-optimality of PCA for spiked
random matrices and synchronization. arXiv:1609.05573, Sept. 2016.
[45] Y. Polyanskiy and Y. Wu. Lecture Notes on Information Theory. Feb 2015. http://www.ifp.illinois.
edu/∼yihongwu/teaching/itlectures.pdf.
[46] N. Srebro, G. Shakhnarovich, and S. Roweis. An investigation of computational and informational
limits in gaussian mixture clustering. In Proceedings of the 23rd International Conference on Machine
Learning, ICML ’06, pages 865–872, New York, NY, USA, 2006. ACM.
[47] S. Vempala and G. Wang. A spectral algorithm for learning mixture models. J. Comput. Syst. Sci.,
68(4):841–860, June 2004.
[48] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices.
arxiv:1011.3027, 2010.

Arxiv preprint

[49] N. Verzelen and E. Arias-Castro. Community detection in sparse random networks. arXiv preprint
arXiv:1308.2955, 2013.

36

