Summary and Contributions: The authors consider the recovery problem for spiked Wigner model. Assuming that the spike is sparse, the authors prove a sharp phase transition in the mutual information of the spike and the data. It is also proved that the mean-square error of AMP algorithm exhibits a phase transition that is different from the transition of the mutual information.
Strengths: The authors rigorously analyze the sparse spiked Wigner model and find the correct scaling of the critical SNR. The analysis is profound and can be adapted in other related problems.
Weaknesses: In its current form, the scaling regimes for the statistical phase transition and the AMP phase transition do not match, and thus the statistical-to-algorithm gap is not proved. It is desirable to mention whether the condition \beta<1/6 is simply a technical one or not.
Correctness: The claims seem correct, but I did not check all the detail in the supplementary materials.
Clarity: The paper is very clearly written.
Relation to Prior Work: It is clearly discussed in the introduction.
Reproducibility: Yes
Additional Feedback: In Theorem 1, the limit of the mutual information is given as the infimum of the potential function. I guess it would be better if it is written in terms of the singular function given in line 213, since the authors focus the Bernoulli and Rademacher-Bernoulli cases only. It is rather unusual that a theorem is given in the appendix. edit: I have no further change in my review after rebuttal.
Summary and Contributions: The authors studied the sparse spiked Wigner matrix model in the case where the number of non-zero entries is sublinear compared to the size of the system. The result obtained by the authors was heuristically found in ref. [52] expanding the result for a number of non-zero entries that scales a the input dimension. The authors present a rigorous derivation of the result.
Strengths: The sublinear sparsity regime is poorly understood from the theoretical point of view. Therefore the result presented in the manuscript is an interesting contribution to the field. The techniques presented could eventually be extended to deal with more complex models.
Weaknesses: Nothing to report.
Correctness: Claims and methods are correct.
Clarity: The paper is well written. ----- I agree with the other reviewer that was frustrating not to read the scaling on the SNR for several pages in the paper. I would appreciate if the authors put forward the information since the beginning.
Relation to Prior Work: Previous works are reported and the contributions are clearly discussed.
Reproducibility: Yes
Additional Feedback: The supplementary should be reorganized to contain only the appendix.
Summary and Contributions: The authors present a rigorous analysis of mutual information and AMP for estimation sparse, rank-one matrices from iid Gaussian noise corrupted measurements in the sublinear sparsity regime.
Strengths: The mathematical depth of the paper is significant.
Weaknesses: The topic is quite far from the interests of most Neurips attendees.
Correctness: Although I did not check the proofs, the results appear to be correct and agree with previous non-rigorous analyses.
Clarity: There are several places in the introduction where improvements can be made. The term "true sparsity" as used on page 2 is very confusing and should be avoided. The authors are simply talking about sparsity in the sublinear regime. Please stick to the standard terminology. The details of the sublinear regime do not appear until page 4. As a reader, I was frustrated with the lack of information about the behavior of $n rho_n$ as $n$ tends to infinity. All we are told is that it does not grow to infinity. As described around (2) and (3), the authors prove that phase transitions exist for particular sequences of $lambda_n$ and $rho_n$. The reader is left wonder about what happens with other sequences. I would think that it is possible to prove that no phase transition exists for some sequences, which suggest that a table could be made to catalog when phase transitions exist, when they don't exist, and when the behavior is unknown. I am confused by the statement in line 188: "as long as $rho_n -> infty$". In the previous paragraph, the quantity $rho_n$ had very specific rates of decay with $n$, while here the claim seems to be for any rate of decay. This could benefit from some clarification.
Relation to Prior Work: The most closely related work is well discussed. However, the authors seem to give the impression that sublinear sparsity is a very new idea and discussed only in 2 papers. In fact, it is well studied, but perhaps not in the same way that the authors study it. Thus, the paper would benefit from a more complete discussion of prior work on sublinear sparsity analysis.
Reproducibility: Yes
Additional Feedback: ** I have read the other reviews and the author's response, and my opinion remains the same. **