Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: # Strengths

- *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.

- *Clarity*: The simulations for the large-sparsity regime and discussion are helpful for understanding the complex behavior of this problem as the sparsity varies.

# Weaknesses

- *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. 

- *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. 

**Edit 08/19:** After discussion with authors, the previous point is resolved.

- *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. 

- *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. 

# Minor issues

- 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. 

- 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).

- Consider making the boundaries bolder in Figure 1. Also I found the color of $\lambda_{it}$ to be hard on the eyes

- Line 70: Typo "statitiscal"

- Line 85: Typo "analyis"

- Line 91: Typo "Statistics", change to "statistics"

- Line 111: Change to "In particular, [10] conjectured and [11] proved..."`

- 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). 

- Line 195: Typo "Invextigate"

- Line 261: Replace "Despite of this fact" with "Despite this fact"

# Summary of score

My 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.

# Update of score 08/19

The 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. 
 
questions: **1.** Is it possible to understand intuitively why the algorithmic threshold does not depend on $\rho$?

**2.** "The state evolution equations (17) coincide exactly with running gradient descent
175 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.

**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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 




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.

questions: I have the following comments on details:
(1) Line 12 in the Abstract: "require" might be "requires"?
(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?
(3) Line 53: the second "is" might be "in"?
(4) Line 84: "arise" might be "arises"?
(5) Line 138: "allow" might be "allows"?
(6) Line 177: is it "closest to"?
(7) Line 195: "invextigate" might be "investigate"?
(8) Line 204: is it "have access to"?
limitations: The limitations of the work are already discussed in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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)$.
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.

The 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. 
questions: -- Could the authors explain how the subspace clustering problem is exactly equivalent to the Eq. (4)?

-- 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.

-- Abstract and l.107: could you explain what subextensive means in this context? (is it related to sublinear?)

-- 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.



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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

Weaknesses: The originality is somewhat limited as main theoretical results are based on previous results. The writing is not entirely clear.
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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths：

1. This paper provides an exact asymptotic characterization of the MMSE in the high dimensional limit. 

2. 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. 

3. It shows that the SNR threshold below which recovery is statistically impossible. 

4. The results in this paper solve an apparent contradiction due to the scaling assumption of the sparsity level with the dimension of the features.  

5. The findings of this paper are verified by algorithms for subspace clustering such as sparse principal component analysis and diagonal thresholding. 

Weaknesses

This 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. 
questions: 1. Please briefly explain the meaning of the indicator vector in Eq.(3).

2. 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.

3. 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.

[OAMP] J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020–2033, 2017.
[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.
[CAMP] K. Takeuchi, “Bayes-optimal convolutional AMP,” IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4405-4428, July 2021.
[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.
review_title: null

Meta-review: metareview: The reviewers appreciate the solid theoretical results concerning statistical-computational tradeoff in subspace clustering. The exact asymptotics and clear presentation make the paper stand out. Therefore, I recommend acceptance. Meanwhile, please carefully revise the paper according to the reviews to highlight its strengths and originality.
confidence: Certain
Decision: Accept