Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap
Authors: Luca Pesce
Bruno Loureiro
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2022 Accept (2022)
Keywords: Replica method
Approximate Message Passing
Statistical Physics
Statistical-to-Computational Gap

Abstract: A simple model to study subspace clustering is the high-dimensional $k$-Gaussian mixture model where the cluster means are sparse vectors. Here we provide an exact asymptotic characterization of the statistically optimal reconstruction error in this model in the high-dimensional regime with extensive sparsity, i.e. when the fraction of non-zero components of the cluster means $\rho$, as well as the ratio $\alpha$ between the number of samples and the dimension are fixed, while the dimension diverges. We identify the information-theoretic threshold below which obtaining a positive correlation with the true cluster means is statistically impossible. Additionally, we investigate the performance of the approximate message passing (AMP) algorithm analyzed via its state evolution, which is conjectured to be optimal among polynomial algorithm for this task. We identify in particular the existence of a statistical-to-computational gap between the algorithm that requires a signal-to-noise ratio $\lambda_{\text{alg}} \ge k  / \sqrt{\alpha}$ to perform better than random, and the information theoretic threshold at $\lambda_{\text{it}} \approx \sqrt{-k \rho \log{\rho}}  / \sqrt{\alpha}$. Finally, we discuss the case of sub-extensive sparsity $\rho$ by comparing the performance of the AMP with other sparsity-enhancing algorithms, such as sparse-PCA and diagonal thresholding.

Subspace clustering in high-dimensions:
Phase transitions & Statistical-to-Computatttaall gap
Luca Pesce"
École Polytechnique Fédérale de Lausanne (EPFL)
Information, Learning and Physics lab.
Bruno Loureiro
École Polytechnique Fédérale de Lausanne (EPFL) Information, Learning and Physics lab.
Florent Krzakala
École Polytechnique Fédérale de Lausanne (EPFL)
Information, Learning and Physics lab.
Lenka Zdeborová
École Polytechnique Fédérale de Lausanne (EPFL)
Statistical Physics of Computation lab.
Abstract
A simple model to study subspace clustering is the high-dimensional k- k-Gaussian mixture model where the cluster means are sparse vectors. Here we provide an exact asymptotic characterization of the statistically optimal reconstruction error in this model in the nigh-dimensional regime with extensive sparsity, i.e. when the fraction of non-zero components of the cluster means p. as well as the ratio a between the number of samples and the dimension are fixed, while the dimension diverges. We identify the information-theoress ing a positive correlation with the true cluster means is statistically impossible. Additionally, we investigate the performance of the approximate message pass- ing (AMP) algorithm analyzed via its state evolution, which is conjectured to be optimal among polynomial algorithm for this task. We identify in particular the existence of statistical statistical-to-compuutte to-computational gap between the algorithm that requires a signal-to-noiss ratio Aalg 2 k/ o to perform better than random, and the infor- mation theoretic threshold at A x kp log p/ / a. Finally, we discuss the case of sub-extensive sparsity by comparing the performance of the AMP with other sparsity-enhancing algorithms, such as sparse-PCA and diagonal thresholding.
threshold below which obtain-
Introduction
With the growing size of modern data, clustering techniques play an important role in reducing the dimensionality of the features used in modern Machine Learning pipelines. Indeed, in many tasks of interest ranging from DNA sequence analysis to image classification, the relevant features are known live in dover-dimensional space (intrinsic dimension) than their acquisition format (extrinsic dimension) [1]. In these cases, identifying these features can help saving computational
"luca.pesce "luca.pesco@cppl.ch
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

resources while significantly improving on learning performance. But given corrupted embedding of low-dimensional features in a high-dimensional space, is it always statistically possible to retrieve them? And if yes how can reconstruction be achieved efficiently in practice? In this manuscript we address these two fundamental questions in a simple model for subspace clustering: a k-cluster Gaussian mixture model with sparse centroids. In this model, the low-dimensional hidden features are given by the sparse centroids, which are embedded in a higher dimensional space and corrupted by additive Gaussian noise. We assume that the number of non-zero components of the centroids as well as the number of samples scales linearly with the dimension of the embedding space. Given finite sample from the mixture, the goal of the statistician is to cluster the data, i.c. estimate the centroids (or features) as well as possible.
Model & setting
Let Zv VE [n] = {1,... ,n} denote n i..d. data points drawn from an isotropic k-clustter Gaussian mixture:
EPO (VYoouesa), CEC
By Lidd
E [r]]
(1)
where Pe. are the class probabilities, C is the index set (C) = k)), Me Rdd are the 8-sparse vectors representing the means of the clusters and Ả is a measure of the signal-to-noise ratio (SNR) for this model. In the following, we focus in the balanced case for which Pe 1/k. We select the subspace of relevant features thanks the introduction of the vector v, R The projection of all the cluster means, on a given dimension E [d], will be completely determined by a linear combination of the components of v,. We consider for this purpose Gauss-Bernoulli distribution:
v. i.d.d. pN Ik) + (1-p) p)o0
(2)
where o == #/a is the density of non-zero elements. For the convenience of the theoretical analysis that follows, it will be useful to work with a particular encoding of the class labels C. For a given sample E [ri] belonging to the class c E C, define the following label indicator vector un E k
1 (-1 k
1,
k
(3)
e-th element
For given draw (αn)ve(n), define the matrices X Rdx with columns given by œy and U
Boxk E Baxk with rows given by un and v,,
crucial point that we shall exploit in this paper is that, with this notation, our model for subspace clustering can be written as a matrix factorization problem, where the data has been generated as:
VUT + W
x
44)
with W E RRdx a Gaussian matrix with elements Wi NN(0, 1). This formulation is completely equivalent to the one in eq. (I), by identifying the cluster means as given component wise by: v. = v._ Uh: i [d]. The centroids will have, in expectation, only non-zero components; as discussed in the introduction, the s-sparse class means [Ma, Joec can be thought of as low-dimensional features embedded a higher-dimensionall space Rd that have been corrupted by isotropic additive Gaussian noise with variance ~ -- Given finite draw (æp)ve(n) generated from this model with class means V. and labels U., the goal of the statistician is to perform clustering, i.e. to estimate U. from X, which is equivalent to retrieving the class label for each sample in the data. However, note that there is a clear class symmetry in this problem: the labels can only be estimated up to a permutation E SCm(C) reshuffling the columns of U,. Taking this symmetry into account we can assess the performance of an estimator Ü through the averaged symmetrized mean-squared error:
MSE(Ü)= = min -B] - U.IIF
where ||1| denotes the matrix Frobenius norm. In particular, we will be interested characterizing reconstruction in the proportional digh-ddme limit where the number of samples the ambient

---

dimension d and the sparsity level go to infinity n. d, s + oc at fixed density p = */d, sample complexity a = %/d, number of clusters & 2 2 and signal strength À > 0.
Note that the clustering problem above is closely related to the problem of estimatinn the class means / features V. Indeed, written as in eq. (4) the problem of estimating both the labels and centroids (U., V.) boils down to a low-rank matrix factorization problem. In this manuscript, we have chosen to frame the discussion in terms of the clustering, but all our results could be presented also in terms of the reconstruction of the class means.
In this manuscript provide sharp asymptotic characterization of when reconstruction, measured by positive correlation with the ground truth, is possible in high-dimensionn for this model, both statistically and algorithnically. In particular, main contributions are:
We map the subspace clustering problem to an asymmetric matrix factorization problem. We compute the closed-form asymptotic formula for the performance of the suyesian-optimal estimator in the high- dithhmmmeniinnl limit, building on a statistical physies inspired approach [2] that has been rigorously proven in this case [3, 4] This allows us to provide sharp threshold bellow which reconstruction of the features is statistically impossible as a function of the parameters of the model. To estimate the algorithmic limitations of reconstruction, we analyse a tailored approximate message passing (AMP) algorithm [2. 5, 6] approximating the posterior marginals in this problem, and derive the associated state evolution equations characterising its asymptotic performance. Such algorithms are optimal among first order methods [7, 8)) and therefore their reconstruction threshold provides a bound on the algorithmic complexity clustering in our model.
The two results above allow us to paint a full picture of the statistical toaeollttt-llgrttiiii trade-offs in high-dimensien to identify an algorithmically hard region of the sparsity level (1 - p) vs. signal-to- plane for which reconstruction is possible statistically but not algorithmically, see Fig. 1. Further, we provide a detailed analysis in the high sparsity regime (p- - 0+) of how the algorithmically hard region grows
subspace clustering for the sparse k-Gaussian mixture model, and in particular
ratio (A)
increase the number of clusters and the sparsity level. In particular, the information theoretical transition arises at An & p/ and the algorithmic one at Aalg 2 k/Vo..
The analysis for AMP optimality relies on the finite P assumption as n, d - DO. We thus also investigate the complementary case when the number of non-zero components is of the order S n and indeed see that sparse principal component analysis (SPCA) and Diagonal thresholding [9] can perform better than random in this region. We find, however, that this requires s S /n (thus o o()). We rephrase our findings in terms of existing literature on the subspace clustering for two-classes Gaussian mixtures [10, 11].
Related works: Subspace clustering is well-studied topic in classical statistics, with a wide range of methods used in practice, see [12] for a review. Closer to this work the theoretical line of work studying the limitations of clustering in high-dimensions. Baik, Ben Arous and Péché have shown that PCA for Gaussian mixture clustering fails to correlate with the mixture means below certain threshold known as the BBP transition
[13]. For dense Gaussian means, the statistical and algorithmic limitations of clustering were analysed in different regimes of interest. Our approach to study subspace clustering relies on mapping to low-rank matrix factorization problem. Low-rank matrix factorization has been extensively studied in the literature, and its asymptotic Bayes-optimal performance was characterized in [2-5, 14-16). The construction of AMP algorithms and the associated state evolutions for matrix factorization was done in [2. 5, 6, 17]. In this work, we leverage these general results on matrix factorization. The closest our work is perhaps [2, 18), where the authors characterize the asymptotic reconstruction thresholds for the dense case (p- = 1) in the proportional limit where the number of samples and input dimensions diverge Non-asymptotic results were also discussed in [19] which considered a modification of Lloyd's algorithm [20] achieving minimax optimal rate and proving a computational lower bound. To the best of our knowledge, the case in which the means are sparse has only been analysed in the regime where the number of non-zero components is sub-extensive with respect to the input dimension. Lower bounds for the statistically optimal recovery threshold in this regime were given in [21, 22]. while computational lower bounds are studied in [23, 24). Clustering two component Gaussian mixtures has been studied in order to shed light on comparison between statistical and algorithmical tractability in a sparse scenario in [10, 11, 25). In particular, [10] conjectured and [1 I] proved algorithmic bounds for this problem. They claim that even below the BBP threshold they can build an algorithm
constant rate.
3

---

1.4
1.2
1.0
0.8
0.6
Aaig
Ant
0.4
Hard phase
Easy phase
Impossible phase
0.0
0.05
0.10
0.15
0.20
0.25
0.30
0.35
P
Figure 1: Phase diagram for the subspace clustering of two-clusters GMM at fixed 2. We plot the SNR À as function of and we rescale the y-axis by valk. We colour different region of the figure according the associated phase. The algorithmic threshold >alg the solid line magenta while the information-theoree
threshold A is the dashed line in cyan. In the impossible region, no method can perform better than a random guess. In the hard region, partial reconstruction of the signal is theoretically possible, but we do not know of any polynomial time algorithm that can do it. In the easy region, however, AMP, can achieve positive correlation with the ground truth (and actually achieves Bayes MMSE, except very close to the tri-critical point, see the discussion in App. A)
achieving exponentially small misclustering error, given that (up-to log factors) we have S Vn. We relate our findings to their work exploring the extreme sparsity regime detail.
3 Main theoretical results
In this section, we introduce the two main technical results allowing us to characterize the limitations of clustering reconstruction (both statistically and algorithmically) for the model introduced above in the proportional high-dimensional limit.
Statistical reconstruction:
First, note that up to the permutation symmetry, the estimator minímiz- ing the averaged gqean-suareed error in eq. (5) admits closed-fom solution given by the marginals of the posterior distribution:
Üno arg min MSB(U)- = E [U]X] UER x
(6)
where the posterior distribution for the model defined in eq. (4) explicitly reads:
P(UIX)
II P. (u, Z(X)
1
/ II R4
dv. (dv,P, (v))
IIII (xx1 (2uT.))))..) ==1==
i=1
and for convenience we defined the vectors u. v2 E R which are the rows of U, V, and with the prior distribution P. being the uniform distribution over the indicator vectors defined in eq. (3) and P, given by the Gauss Bauss-Bernouilli distribution defined in eq. (2).
Although in principle it would be possible to compute the minimum mean- mean-squared error (MMSE) given by the Baycs-optimal estimator in eq. (6) by sampling from the posterior from eq. (7), this impractical when d, n are large. For instance, simply computing the different integrals involved in the evidence scale exponentially with the dimensions. The first result consists precisely in closed-form solution for the asymptotic performance of the Bayes-optimal estimator:
Main theoretical result In the proportional high-dimensional limit where n. d, Do with fixed ratios p = s/d, n/a and fixed X, k, the minimum mean- mean-squane squared error for the reconstruction of U E Bunk is given by:
k 4
lim MMSE n00
Tr M"
(8)

---

where M E kx is the solution of the following minimization problem:
M arg min M. ERAXE
max (M.RAAA
Des (Mu,
with:
aA Tr Mi
adMu adMau
a.Mu
Ev,,
log Zu
w
2p
P
p
AMp 2M
AM w
a Bun,w
log Zu
(10)
where introduced u, Pas Ux
Po.
Is). and we defined Zufo o as:
Za(A,b) Σ
exp
b bTue- u Alte)
(11)
EEC
bb (T (/s + AA
b) = p pexp
V det (Ix + A)
(12)
2
Result follows from mapping of the subspace clustering problem introduced in Sec. to low-rank matrix factorization form eq. (4). Indeed, this mapping allows us to leverage closed-form formula characterizing the asymptotic MMSE for low-rank matrix estimation with generic priors that was derived heuristically [2, 18] using the replica method from Statistical Physics and was rigorously proven in series of works [3-5, 14] in the context of subspace clustering. Our contribution resides in making this connection and drawing the consequences for the subspace clustering problem, non-trivial endeavour given the complexity of the resulting formulas. Note that the minimization problem eq. (9) is fundamentally different from the one in eq. (6). Indeed, the first involves only low- dimensional variables, and can be easily solved in a computer, while the latter is high-dimensionall problem which is computationally intractable for large d, n. The other parameter M E k solving eq. (9) can be used characterize the MMSE reconstruction error on V.
Algorithmic reconstruction: While result allow us to sharply characterize when clustering is statistically possible, it does not provide practical way to estimate the true class labels U, E Ra*k from the data E Rdx" In order provide bound in the algorithmic complexity clustering. we consider approximate message passing (AMP) algorithm for our problem. Message passing algorithms are class of first order algorithms (scaling as O(nd), the dimensions of the input matrix X) designed to approximate the marginals of target posterior distribution, and which have two very important features. First, for a large class of random problems (such as the clustering problem studied here) AMP provides the best known first order method in terms of estimation performance [26-30], and has been rigorously proven to be the optimal for certain problems [7, 8]. Second, the asymptotic performance of AMP can be tracked by a set of low-dimensional state evolution equations [31], meaning that its reconstruction performance can be sharply computed without having to run a high-dimensional instance of the problem. For low-rank matrix factorization problems associated AMP algorithm can be derived [5, 6, 17, 32, 33]. Therefore, yet again we leverage the mapping of subspace clustering low-rank matrix factorization problem derive the associated AMP algorithm with denoising functions Tee Ju:
Tu (A, b)
Ed exp (Tu, u. Σ Uc exp b Uh
1
u Aua
(13)
2
(Is + A)
(A, b)
(14)
p (1- (1-p))dde (1, A) exp
Axx
bb [bb(l(tA)
(l+t)) 36
2
As mentioned above, one of they key features of Algorithm is that its asymptotic performance can be tracked exactly by set of low-dimensional equations.
5

---

Algorithm 1 low-rAMP
Input: Data E Rdxn Initialize " ui No,,,, cls), 6l.00
0xx -1=0 OR
for & I max do
A
( U,
A = (V)) V
B = V X2X - O vi-
By V
Σ
d
v,
of 0'1
v=1
1=1
Take (b', E ERR ri=1: (b
E ER" rows of B B
of-1 n/ (A b),)),
uy
= (A b(,))
ofit (A, byye).
T = OoTalA by
Here U' Bunk V E Bddx By E Bank By E Buxk A E B A e R
end for Return: Estimators Vamp,i, Uamp, R ou δud E l
Main theoretical result 2 In the proportional high-dimensional limit where d, 0o with fixed ratios p = */d, a = n/d and fixed X, ki the correlation between the ground truth (U., V.) and the
AMP estimators (0 Uamp: amp) at iterate t,
M 1 U_ U amp-
1 VT M n
aamp
(15)
satisfy the following state evolution equations:
adMu a.Muu.
aaMM
M -..
na
w
u
(16)
P
p
p
AM
UM P
AM,
M = We..
The
+
w
V.
(17)
p
Moreover. the asymptotic performance of is simply given by: lim MSE(U n1+000
k Tr MrM
(18)
k
Result 2 is a consequence from the general theory connecting AMP algorithms to their state evolution (SE) [31]. In the context of low-rank matrix factorization, derivation of the state evolution equations above from Algorithm were first provided for the rank-one case in [5, 6] and were extended to gen- eral rank and denoising functions in [2, 18). A crucial observation is that Result 2 is intimately related to Result 1. Indeed, the state evolution equations (17) coincide exactly with running gradient descent on the potential defined in eq. (10). While the performance of the statistically optimal estimator Üho is given by the fixed point with the minimal value of the potential 4,.. the performance of the AMP estimator Üamp is described by the closest minima to the initialization MC= Therefore, studying both the statistical and algorithmic limitations of clustering in high-dimensions boils down to the study of the minima of the potential Φn. see App. A for further details. The identification of a subspace clustering problem with a matrix factorization one allows us to leverage the rich literature from this field. However, analyzing these formulas is far from trivial and consitutes a considerable technical challenge. The major difficulty is to find a suitable parametrization of the overlap matrices that reduces the number of parameters to be tracked, we discuss this in detail in Sec. 5. Moreover, we find the scaling ansatz in the sigh-sp limit that closes the equations on amenable quantities in order find analytically the satistical-to-comee to-copuutational gap for the large-rank setting, see Sec. However, we stress that we did not take all the necessary precautions to claim full rigor. c.g. prove formally that the minimum is unique (although we checked all these both analytically and numerically).
4 Reconstruction limits for sparse clustering
These results allow us to paint full picture for when sparse subspace clustering possible in the model defined in Sec. 2 as function of the quantity of data the sparsity 1-p, the number of clusters

---

k and the SNR A. Figure/ summarizes the different reconstruction regimes in the (p. X) plane for a two-clusters problem fixed sample complexity 2, also known as a phase diagram. Moreover the general considerations on the reconstruction limits for sparse clustering, given by analyzing the two-clusters problem, are easily generalizable to the general mixture case and not restricted to that particular model, see Sec. 5. For fixed sparsity 1 1-p, we identify the following regions in Fig. 1:
Impossible phase: There is not enough information in the data matrix X handled to the statistician to assign cluster membership better than chance for any algorithm. The Bayes-optimal MMSE is not better than a random guess. Clustering (reconstruction of U. better than chance) is impossible.
Hard phase: The MMSE is non-trivial, and clustering is statistically possible to some extent, but the best known polynomial time algorithm, AMP, fails to correlate better than chance with the true cluster assignment U.. Any polynomial-timg -immiell--meeeeeee algorithm is conjectured to fail in this region.
Easy phase: In the easy phase, not only clustering is statistically possible, but AMP is able to achieve positive correlation with U.. One can also investigate when AMP achieves the Bayes-optimal MMSE (instead of just positive correlation) leading the same transition (except from subtle correction very close to the tri-critical point, see the discussion in App. A).
In Fig. 2, we investigate the different phases presented above by varying the sparsity level - p and SNR at fixed az We compare the performance of AMP with popular spectral algorithms: Principal Component Analysis (PCA) and Sparse Principal Component Analysis (SPCA). We can initialize AMP and the SE equations in two different ways: we call uninformative initialization a choice for the first iterates of AMP and SE which assumes no knowledge on the ground truth values; conversely with informative initialization we consider that the statistician has some prior knowledge on the the ground truth signal. Note that in a real-life scenario the statistician does not have access the ground truth. Yet, as theoretical tool the informative initialization provides important information about the algorithmically hard phase, see App A for a discussion. The initialization strategy we considered in the uninformed case for Algorithm 1 is not the only possible choice. there are smarter ways of initialising which can lead to a considerable improvement without explicitly assuming any information about the signal, e.g. spectral initialization [34]. Looking at Fig. 2 we see that SE with uninformed initialization tracks AMP. Morover we note that increasing the sparsity level, iee decreasing p. the problem becomes algorithmically harder. This is reflected in discontinous jump in the MSE at Aalz which becomes larger. We observe along the same lines a neat advantage by imposing the sparsity constraint in the spectral algorithm (SPCA) with respect to vanilla one (PCA) as the sparsity grows. We discuss the details on the numerical simulations in App. and the code is available at
5 Stability analysis and algorithmic threshold
In this section we provide a detailed analytical derivation of the threshold Aaig characterizing the algorithmic reconstruction function of the number of clusters and the sparsity. First, note due to the permutation symmetry of the clusters the overlap matrices admit the following parametrization:
m u h
m
m
M
JR
M
m Ja
JR
(19)
where J& is the ls x k-matrix with all elements equal one. This parametrization is preserved under the SE iterations. Therefore, inserting it in the SE equations yield equations for (m m!):
my .+1 = (/ (Am²/fp)
++1 my
(a>mi//))
(20)
where we introduced the following update functions:
k
e v7
(1) k- Bu.-Nio.La))
(21)
Amss+uiV= + ewIvE
k
p²z
Sk-1 (2T) p + (1- p)( (
62/2
(z) = kik +2)
c2a dg 2
(22)
where Sk-1 is the surface of the k-dimennional unitary hypersphere. Recall that (m, m)) (0, 1]2 fully characterize the reconstruction performance, with (m m = (0. 0) corresponding to the per- formance of random guess. Conversely, (m .m,))= p1, corresponds to perfect reconstruction
7

---

Fixed p= 18%
b) Fixed p 555%
1.0
0.9
0.9
0.8-
0.8
0.7
Informative
informative
SE Uninforrmatvee
SE. Vninfermative
0.5
Aay
Aata
0.4
Aa
0.4
Ad
SPCA
SPCA
0.3-
PCA
0.3-
PCA
AMP
0.2
0.25
0.50
0.75
1.00
1.25
1.00 Ava
1.25 1.50 1.75
/va
Figure 2: We compare the performance for clustering of two-classes GMM, as measured by the MSE of AMP, SPCA, PCA and SE informed and uninformed. We plot the MSE as function of the SNR and we rescale the x-axis by vajk. For each algorithm considered the error bars are built using the standard deviation over fifty runs with parameters (n 8000, d = 4000), i.e. a 2. We plot in vertical line the theoretical values for the Information-Theereti threshold An (dashed cyan line), and the algorithmic threshold Alg (dotted line in magenta). The theoretical values coincide with the experimental one. The SE with uninformed initialization follows AMP as expected. Left: The sparsity is fixed with parameter o = 18%. Both SPCA and PCA have worse performance with respect to AMP and in this sparsity regime we have only a marginal advantage by using SPCA with respect to PCA. Right: The sparsity fixed with parameter p = 5%. Increasing the sparsity level the width of the algorithmically hard phase becomes bigger and SPCA performs clearly better than PCA.
of the cluster membership and the sparse cluster means. One check that the trivial fixed point (m.,, m.) = (0, 0) is always a fixed point of the SE equations. Moreover, note that its stability is cru- cially connected to the algorithmic threshold Aulg- Indeed, if the trivial fixed point (m,, m,) = (0, 0) is stable, AMP with an uninformed initialization will always converge to this point and therefore achieve random guessing performance. To study its stability, expand the update functions around (Mu, m.) = (0, 0) up to the second order. Expressing everything in terms of my. we obtain:
X²a m + ( (l 4) 122
X²a2
++1 F's (m²) m
(m²)² + ((m)))
(23)
2
13
This immediately tells us that the trivial fixed point becomes unstable at the algorithmic threshold Xalg = k/Va.. This transition is well-known result in random matrix theory and goes under the name of BBP transition [13]. Despite the fact that we expand around the trivial fixed point, the perturbative method also provides information also about the Bayes-optimal performance, thanks to the general properties that the phase diagrams in Bayes-optimal inference problems must respect [35]. Indeed, sufficient criterion for the presence of an algorithmically hard phase requires at the algorithmic threshold: F (0) > O. The local study predicts that the phase diagram will present an algorithmically hard region for k > knard 4 2 a. The criterion nevertheless is not necessary in this setting, immediately see from the phase diagram for the two-components GMM in Fig. 1: we clearly observe an algorithmically hard region for high-sparsity although k < Khard- In fact, the information-theorel threshold An. defined as the value of the SNR at which the problem becomes statistically possible, cannot be found simply thanks to the expansion around the trivial fixed point. Indeed the exact com- putation of A requires evaluating the potential function + in eq. (10): one needs to find the threshold value of the SNR at which the informative fixed point has lower value of the free energy with respect to the uninformative fixed point. The technical discussion on the calculation of Ait which we see plotted in Fig. 1 for the two-classes case, given in App. B, while general overview on the different thresholds is given in App. A. It is interesting to stress that the linearization of the SE equation around the trivial fixed point in eq. (23) coincide to study the gradient of the potential 4 in eq. (10) around that point, and hence the stability of the trivial fixed point is determined by the potential landscape. This connection is at the roots of the conjectured link between the hardness of an inference task and AMP: the potential in eq. (10), describing the performance of the Bayes-optimal estimator, is attained far from locally stable region around the uninformative fixed point, where the AMP algorithm gets stuck.
gap opens up as the fixed point with minimal value of the
8

---

a) Fixed ratio d=
b) Fixed ratio a
0.8
0.8
0.7
MS
0.7
d-500
0.6
d-500 DT
d=:00 SPCA
d=500 SPCA
d=1000 SPCA
d=1000 SPCA
d-2000 DT
d-2000 DT
0.4
0.4
d=2000 SPCA
0.4
0.6
0.8
1.0
1.2
s/VII
s/vm
Figure 3: We compare the performance of diagonal thresholding (DT) and Sparse PCA (SPCA), as measured by the MSF, for clustering of two-classes GMM for two different parameter We plot the MSE vs the number of non-zero component s and we rescale the x-axis by the square-root of the number of samples. The left plot is done a while the right one is for a 2. 2.ehe SNR is tuned such that we are always under the BBP threshold. With this choice we always work in the sub-extensive sparsity regime o o(1) and we can verify numerically what has been claimed in the literature [10, I1]: efficient algorithms in the high dimensional limit need number of non-zero component (up-to log factors) S vni in order to beat random guessing under the BBP threshold.
Large sparsity regime
We characterize in this section the scaling of the thresholds in the very sparse (and most interesting) regime when + 0+. We highlight the main passages of the computation and focus on the principal results, see Appendix C for a detailed analysis. The starting point is the following change of variables:
p log
p log
ma m.,,
m. = m.
A = C(k)k)
(24)
Inserting these expressions into eq. (20), we obtain simplified SE equations for the rescaled overlaps (mu myy without any residual dependence (p. a):
my
C(k)m,
my Ta (C(k))na))
(25)
where we introduced the auxiliary function (-(-) defined as:
S ck+ e -2/0 k(2T)**/*
x5² 2 -1) dE
Ti(()) ==
where O(-) is the Heaviside theta function. By considering the large expansion of Tx.+), we can derive the scaling of the ITT threshold with (k, a.), see Appendix C. for more details. Putting together with our previous result for Allg from Sec. 5, we obtain the following fundamental result:
kplog
k
Aalg
(26)
Va
These equations completely characterize the behavior at large rank & small (but finite) sparsity. The gap, where AMP is not able to exploit the information on the sparse nature of the cluster means, grows with both the sparsity and the rank. In App. C, we further show that the large rank expression for the threshold A is accurate already at moderate It is interesting at this point to reframe our results on the high sparsity regime in the context of the existing literature. The results for the IT transition for the detection of two-classes sparse GMM were discussed in [22, 23], and we obtain consistent scaling in the small p behaviour. Despite this fact, algorithmic bounds of different relevant works for the same problem [10, 11, 23] seem, at first sight, to not agree with our findings. In particular [11] proves rigorously the existence of an algorithm that achieves minimax rate under the BBP threshold clustering of two-classes sparse GMM. This apparent inconsistency is related to different sparsity regimes analyzed. Indeed, here we investigate
10, see Fig.

---

the extensive sparsity regime, i.e. = O while the guarantees for the efficient algorithms working under the BBP threshold require a very high sparsity level, i.c. p p= o(1). This difference is crucial. In Fig. 3 we illustrate it by considering the performance of two popular algorithms for this problem: Diagonal Thresholding (DT) [9] and SPCA. For extremely large sparsity, i.e. = (11, these algorithms indeed provide estimators with positive correlation with the true classes below the BBP threshold! However, as soon as we increase the density of non-zero components the performance strongly deteriorates. In fact, the transition to random chance performance takes place as the number non-zero components approach S /ni in agreement with the literature [10, 11].
Conclusion
In this work we considered the problem of clustering &o homogeneous Gaussian mixtures with sparse means. Mapping this to a low-rank matrix factorization problem, we have provided an exact asymptotic characterization of the MMSE in the high dimensional limit. The Bayes-optimal performance was compared to AMP, the best known polynomial time algorithm for this problem in the studied regime. In the large sparsity regime, we uncovered large gap the sparsity level grows, and unveiled the existence of a computationally hard phase. In particular, we have shown that the SNR threshold below which recovery statistically impossible is given by A x Vokplog v/va, while the one for which AMP positively correlates with the ground truth classes given by Aal 2 *//o.. Our result for the existence of algorithmically hard region was compared with the existing literature for this problem, solving an apparent contradiction due the scaling assumption of the sparsity level with the dimension of the features. We corroborated our findings with the help of algorithms for subspace clustering such as sparse principal component analysis and diagonal thresholding. The mapping the subspace clustering problem a low-rank matrix factorization one is flexible and extending this work to more general scenarios is definitely interesting. The main limitation the current setting is the Gaussian assumption for the noise. One natural idea go beyond this limitation is to consider other flavours of message passing algorithms, such as vector AMP (VAMP) [36] to study more general rotationally invariant noise distributions. A further prospective direction is consider inhomegeneous mixture models, i.e. Pe 1/k in eq. (1), in order to study the effect of unbalancedness on the cettiiaalto--coputtationn gap.
Acknowledgment
We thank Maria Refinetti for discussions. This work started part of the doctoral course Statistical Physics For Optimization and Learning taught at EPFL in spring 2021. We acknowledge funding from the ERC under the European Union's 's Horizon 2020 Research and Innovation Program Grant Agreement 71 714608-00 714608-SMiLe, and by the Swiss National Science Foundation grant SNFS OperaGOST, 200021 200390.
10

---

References
[1] Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact learning, 2021.
[2] Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7)0073403, Jul 2017.
[3] Mare Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume of Proceedings of Machine Learning Research, pages 1297-1301. PMLR, 2017.
[4] Léo Miolane. Fundamental limits of low-rank matrix estimation: the non-symmetric case, 2017.
[5] Yash Deshpande and Andrea Montanari. Information-thhcoretiallll optimal sparse pea. In 2014 IEEE International Symposium on Information Theory, pages 2197-2201. IEEE, 2014.
[6] Alyson Fletcher and Sundeep Rangan. Iterative reconstruction of rank-one matrices in noise. Information and Inference: A Journal of the IMA, 7(3):531-562, 2018.
[7] Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods, 2020.
[8] Michael Celentano, Chen Cheng, and Andrea Montanari. The high-dimensional asymptotics of first order methods with random data, 2021.
[9] lain M. Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association, 104(486):682-69) 2009. PMID: 20617121.
[10] Jiashun Jin, Zheng Tracy Ke, and Wanjie Wang. Phase transitions for high dimensional clustering and related problems, 2016.
[11] Matthias Löffler, Alexander Wein, and Afonso S. Bandeira. Computationally efficient sparse clustering, 2021.
[12] Lance Parsons, Ehtesham Haque, and Huan Liu. Subspace clustering for high dimensional data: a review. SIGKDD Explor, 6(1):90-105, 2004.
[13] Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5):1643 1697, 2005.
[14] Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborová, et al. Mutual information for symmetric rank-one matrix estimation: proof the replica formula. Advances in Neural Information Processing Systems, 29, 2016.
[15] Ahmed El Alaoui and Michael I Jordan. Detection limits in the high-dimensional spiked rectangular model. In Conference On Learning Theory, pages 410-438. PMLR, 2018.
[16] Ahmed El Alaoui, Florent Krzakala, and Michael Jordan. Fundamental limits of detection in the spiked wigner model. The Annals of Statistics, 48(2):863-885, 2020.
[17] Ryosuke Matsushita and Toshiyuki Tanaka. Low-rank matrix reconstruction and clustering via approximate message passing. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[18] Thibault Lesieur, Caterina Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zdeborova. Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering. 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Sep 2016.

---

[19] Mohamed Ndaoud. Sharp optimal recovery in the two-component gaussian mixture model, 2020.
[20] Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2):129-377, 1982.
[21] Martin Azizyan, Aarti Singh, and Larry Wasserman. Minimax theory for high-dimensional gaussian mixtures with sparse mean separation, 2013.
[22] Nicolas Verzelen and Ery Arias-Castro. Detection and feature selection in sparse mixture models, 2016.
[23] Jianqing Fan, Han Liu, Zhaoran Wang. and Zhuoran Yang. Curse of heterogeneity: Computa- tional barriers in sparse mixture models and phase retrieval, 2018.
[24] Matthew Brennan and Guy Bresler. Average-case lower bounds for learning sparse mixtures, robust estimation and semirandom adversaries, 2019.
[25] Martin Azizyan, Aarti Singh, and Larry Wasserman. Efficient sparse clustering of high- dimensional non-spherical gaussian mixtures, 2014.
[26] David I.. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914-18919 2009.
[27] Krzakala, M. Mézard, F. Sausset, Y. F. Sun, and L. Zdeborová. caatistiaa-physice--biee reconstruction in compressed sensing. Phys. Rev. X, 2:021005, May 2012.
[28] Jean Barbier, Florent Krzakala, Nicolas Macris, Leo Miolane, and Lenka Zdeborova. Optimal errors and phase transitions high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12)55411-5460, 2019.
[29] Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová. The spiked matrix model with generative priors. IEEE Transactions on Information Theory, (7(2):1156-1183 2021.
[30] Benjamin Aubin, Bruno Loureiro, Antoine Baker, Florent Krzakala, and Lenka Zdeborová. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Jianfeng Lu and Rachel Ward, editors, Proceedings of The First Mathematical and Scientific Machine Learning Conference, volume 107 of Proceedings of Machine Learning Research, pages 53-73. PMLR, 20-24.2 Jul 2020.
[31] Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling, 2012.
[32] Ryosuke Matsushita and Toshiyuki Tanaka. Low-rank matrix reconstruction and clustering via approximate message passing. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[33] Andrea Montanari and Ramji Venkataramanan. Estimation of low-rank matrices via approximate message passing. The Annals of Statistics, 49(1):321 -345, 2021.
[34] Marco Mondelli, Christos Thrampoulidis, and Ramji Venkataramanan. Optimal combination of linear and spectral estimators for generalized linear models, 2020.
[35] Federico Ricci- Tersengerss,hh. Guilhem Semerjian, and Lenka Zdeborová. Typology of phase transitions in bayesian inference problems. Physical Review E, 99(4), Apr 2019.
[36] Sundeep Rangan, Philip Schniter, and Alyson K. Fletcher, Vector approximate message passing, 2016.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.
(b) Did you include complete proofs of all theoretical results? [N/A] Some of the results regard low-rank matrix factorization problems, we use in this case formulas which have been proven rigorously in [3, 4]. On the other hand, heuristic results in the manuscript have been dutifully checked resorting to extensive numerical simulations.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] The code will be released in a mon-anonymuus version of the manuscript.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "sQfH4tGo9Ju", "reviewer": "Reviewer_2rXD", "summary": "This paper studies the performance of subspace clustering in a high-dimensional Gaussian mixture model. The cluster centers are assumed to be sparse. The problem is equivalent to one of low-rank matrix estimation. Using this connections, the information-theoretic limit for this problem is derived and compared with the performance of AMP (generally thought to be the best among poly-time algorithms for this problem).  The results are specialized to the setting of sparsity ratio approaching one, and the statistical-computational gap is found to be of the order of $\\sqrt{\\rho}\\log(1/\\rho)$.", "questions": "-- Could the authors explain how the subspace clustering problem is exactly equivalent to the Eq. (4)?\n\n-- Does the equivalence of subspace clustering to low-rank estimation hold even in the unbalanced case, i.e., when $p_c$ does not necessarily equal $1/k$? Analyzing this general case and exploring the effect of unbalancedness would be one way to increase the novelty of the contribution.\n\n-- Abstract and l.107: could you explain what subextensive means in this context? (is it related to sublinear?)\n\n-- Typos: l.85: \"analysis\" misspelled;  l.128: unpractical --> impractical; l.137-147: I think the references to Eq. (38) should be to Eq. (9)? l. 162, 172 etc. : I think Algorithm 3 refers to Algorithm 1? l.195: \"investigate\" misspelled.\n\n\n", "limitations": "Connections and references to prior work are good overall, but it would be nice to have at least a brief discussion of open questions and generalizations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is generally well written and pleasant to read. Having exact, computable expressions for the asymptotic MMSE as well as the asymptotic overlap of AMP that are validated by numerical simuations is welcome. The scaling behavior in the large sparsity regime and the characterization of the stat-comp gap in this regime is nice.\n\nThe main weakness of the paper is novelty. As the authors acknowledge, all the results in the paper are obtained by evaluating known results for this particular model. In particular, the information-theoretic limits for low-rank matrix estimation (Theoretical result 1) have been derived in a series of  papers including [2,3,4,14], and a perusal of the supplementary material did not reveal any technical challenges in evaluating the known formulas for the subspace clustering model studied here. Similarly, the AMP and the state evolution characterization of its perforamance (Theoretical result 2) are also well known from previous works. Comparing the the IT limits with the AMP overlap just involves running the state evolution equations from two distinct initial conditions -- perfect initialization to obtain the IT limit, and uninformative initialization to obtain the AMP overlap. The behavior in the high sparsity regime is novel and a nice result, but the overall novelty of the paper still falls short. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZKhLrqvsS10", "reviewer": "Reviewer_U268", "summary": "This work explores statistical-computational gaps in the problem of obtaining non-trivial correlation (sometimes referred to as `weak recovery') with the cluster labels of a balanced mixture of isotropic Gaussian vectors that have sparse means drawn from a Gaussian-Bernoulli prior. Via a reduction to a low-rank matrix factorization problem, explicit formulas are derived for the asymptotic mean-squared error of the Bayes estimator, which is statistically optimal for this problem although likely hard to compute. On the algorithmic side, approximate message passing is proposed and an exact asymptotic formula for its mean-squared error is derived. Information-theoretic and algorithmic thresholds are described, and for large enough sparsity levels, these two thresholds differ. Numerical experiments explore what happens when the sparsity level is sub-extensive and show that the phase transitions have a different behavior in this regime.", "questions": "**1.** Is it possible to understand intuitively why the algorithmic threshold does not depend on $\\rho$?\n\n**2.** \"The state evolution equations (17) coincide exactly with running gradient descent\n175 on the potential defined in eq. (40)!\" Is this connection known for other problems? Why is this observation crucial for the results here?", "limitations": "**1.** I agree with the authors' assessment that there are no apparent potential negative societal impacts.\n\n**2.** The weak recovery problem studied here is primarily of theoretical interest, and it is not clear if the AMP algorithm is useful for non-Gaussian problems. So practical impact may be limited.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- *Significance/Quality*: The theorems give a roughly complete understanding of the weak recovery problem, from an information-theoretic and algorithmic point of view, in the linear-sparsity, linear-dimension regime. In particular the algorithmic threshold is identified with a sharp constant factor.\n\n- *Clarity*: The simulations for the large-sparsity regime and discussion are helpful for understanding the complex behavior of this problem as the sparsity varies.\n\n# Weaknesses\n\n- *Originality*: Main Result 1 relies on known formulas for low-rank matrix factorization. It is not clearly explained what are the major technical challenges, if any, in obtaining this result. \n\n- *Clarity*: The community labels in (3) and the model (4) are such that the $\\mathbb{E}X$ does not have sparse columns if $k$ is small. For this reason, I feel the paper is more about the large $k$ version of the sparse clustering problem. \n\n**Edit 08/19:** After discussion with authors, the previous point is resolved.\n\n- *Clarity*: From the main text alone, it is unclear how the information-theoretic threshold is obtained. The formula of the MSE is difficult to interpret, so I can't see if the threshold is a consequence of this. Some further explanation is needed here. \n\n- *Quality/Clarity*: It is difficult to assess the rigour of both main results, especially Main Result 2. This is because the appendix is not organized in a conventional way with a clearly demarcated proof of Main Results 1 and 2. For Main Result 2, I do not see in the Appendix any explanation of how the asymptotic algorithmic MSE is computed. I only see plots rather than arguments. I also do not see any derivation of the Bayes-optimal MSE or reference to known (rigorous) formulas. \n\n# Minor issues\n\n- Line 39: Equation (2) defines vectors that are (i) standard Gaussian with probability $\\rho$ OR (ii) the zero vector with probability $1 - \\rho$. I think what is meant is for there to be a random subset of zero entries, with the rest of the entries being Gaussian. \n\n- Main Theorem 1: Please take a careful proofread over this. Here $\\mathbf{v^*}, \\mathbf{u^*},$ and $\\mathbf{w}$ have not been defined in (10). Also $Z_u$ does not appear in (10).\n\n- Consider making the boundaries bolder in Figure 1. Also I found the color of $\\lambda_{it}$ to be hard on the eyes\n\n- Line 70: Typo \"statitiscal\"\n\n- Line 85: Typo \"analyis\"\n\n- Line 91: Typo \"Statistics\", change to \"statistics\"\n\n- Line 111: Change to \"In particular, [10] conjectured and [11] proved...\"`\n\n- Line 143-144: This comment is hard to understand because (38) is in the Appendix, and then I'm having trouble seeing the connection to (6). \n\n- Line 195: Typo \"Invextigate\"\n\n- Line 261: Replace \"Despite of this fact\" with \"Despite this fact\"\n\n# Summary of score\n\nMy score is due to concerns mostly about the rigor and partially about the novelty of this submission. I also feel there is a lack of clarity in explaining how the main results are obtained.\n\n# Update of score 08/19\n\nThe authors' rebuttal addressed my concerns about rigor and somewhat about novelty. I agree with other reviewers that the strengths and technical challenges of this paper are not highlighted enough in the main text. I also think further clarity is needed on the level of rigor and the asymptotic regime to which the results apply (which seems to be for k growing large and rho going to 0). I have raised my overall score from 3 to 4 because further serious revision is needed. I have also upgraded the soundness from 1 to 2. \n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LSEjJ5hnRpc", "reviewer": "Reviewer_Szix", "summary": "This paper considers a subspace clustering problem as a low-rank matrix factorization problem. The performance of the Bayes-optimal estimator is characterized by the high-dimensional limit. Clearly, the computationally hard phase, easy phase, and impossible phase are provided via an information-theoretical threshold and an algorithmic threshold. Authors also show that the statistical-to-computational gap will grow with both the sparsity and the rank.", "questions": "1. Please briefly explain the meaning of the indicator vector in Eq.(3).\n\n2. In the impossible phase, the Bayes-optimal MMSE is not better than a random guess. Does this statement hold only for the two-clusters problem? or general mixture case also applies.\n\n3. Can the results in this paper apply to more general right-unitarily-invariant noise matrices? Recently, there are some new AMP-type algorithms such as OAMP/VAMP, CAMP, and MAMP that solve more general signal recovery problems with right-unitarily-invariant matrices. The authors may consider extending their work to right-unitarily-invariant matrices.\n\n[OAMP] J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020–2033, 2017.\n[VAMP] S. Rangan, P. Schniter, and A. Fletcher, “Vector approximate message passing,” IEEE Trans. Inf. Theory, vol. 65, no. 10, pp. 6664-6684, Oct. 2019.\n[CAMP] K. Takeuchi, “Bayes-optimal convolutional AMP,” IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4405-4428, July 2021.\n[MAMP] L. Liu, S. Huang, and B. M. Kurkoski, “Memory AMP,” IEEE Trans. Inf. Theory, 20222, early access.", "limitations": "The results in this paper are limited to IID Gaussian noise matrices. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\n\n1. This paper provides an exact asymptotic characterization of the MMSE in the high dimensional limit. \n\n2. In the large sparsity regime, the authors uncover a large statistical-to-computational gap as the sparsity level grows and unveiled the existence of a computationally hard phase. \n\n3. It shows that the SNR threshold below which recovery is statistically impossible. \n\n4. The results in this paper solve an apparent contradiction due to the scaling assumption of the sparsity level with the dimension of the features.  \n\n5. The findings of this paper are verified by algorithms for subspace clustering such as sparse principal component analysis and diagonal thresholding. \n\nWeaknesses\n\nThis paper only works on a low-rank matrix factorization problem with IID Gaussian noise matrices, which limits the applications of the results in this paper to more general right-unitarily-invariant noise matrices. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CZwr5R3TerX", "reviewer": "Reviewer_u83T", "summary": "The authors consider a clustering problem where the cluster means are sparse vectors and the noise is Gaussian. They prove the information-theoretic threshold in terms of the signal-to-noise ratio (SNR) under which the clustering is impossible statistically. They also analyze a performance of an approximate message passing (AMP) algorithm for the problem. The difference between the informatin-theoretic transition and the algorithmic transition (based on the AMP algorithm) is discussed.", "questions": "I would like to see more about the originality and the significance of the work. In the current writing, it gives impression that the current work is merely an interpretation of existing results [3-5, 14]. The model should be explained in further detail. For example, what is the 's-sparse vector' in the first paragraph in page 2?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The authors showed a statistical-to-computational gap for the large (but not very high) sparsity regime where the density of non-zero elements in the cluster mean is of order 1. They provide a detailed analysis between their results and the existing results for the very high sparse regime.\n\nWeaknesses: The originality is somewhat limited as main theoretical results are based on previous results. The writing is not entirely clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3_2I4mesXQ", "reviewer": "Reviewer_a17U", "summary": "This paper studies statistical and computational limits of subspace clustering, focusing on high-dimensional Gaussian mixture model with sparse centroids. The paper considers the regime where both the fraction of non-zero components of the cluster means and the ratio between the number of samples and the dimension are fixed (which differs from previous literature). The information-theoretic threshold (below which reconstruction is statistically impossible) and algorithmic limitations (in terms of an approximate message passing algorithm) are obtained, which indicate a statistical-to-computational gap. The results are illustrated and compared with previous works through simulations. \n\n\n\n", "questions": "I have the following comments on details:\n(1) Line 12 in the Abstract: \"require\" might be \"requires\"?\n(2) Line 36: it would be nice if a definition of \"s-sparse vectors\" can be given here: is it in terms of expectation or deterministic?\n(3) Line 53: the second \"is\" might be \"in\"?\n(4) Line 84: \"arise\" might be \"arises\"?\n(5) Line 138: \"allow\" might be \"allows\"?\n(6) Line 177: is it \"closest to\"?\n(7) Line 195: \"invextigate\" might be \"investigate\"?\n(8) Line 204: is it \"have access to\"?", "limitations": "The limitations of the work are already discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The analysis of statistical and computational limits and the resulting phase diagram in this paper is an interesting contribution to the study of high-dimensional Gaussian mixture models and subspace clustering. The regime that the paper focuses on (extensive sparsity: the fraction of non-zero components of the cluster means is fixed) is different from that in the previous literature (where the fraction of non-zero components of the cluster means goes to 0). Many of the theoretical results are adapted from existing analysis on statistical and computational limits of low-rank matrix factorization, although the idea that statistical and computational limits of Gaussian mixture model can be connected to low rank matrix factorization is new. The ideas and results are clearly presented in the paper, and the phase diagram and simulation studies give good illustrations to the statistical-and-computational gap.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept