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 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 ρ
OR (ii) the zero vector with probability 1 − ρ
. 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 v ∗ , u ∗ , and 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 λ i t
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.
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.
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.