- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies a sketched power method for the spectral-norm low-rank approximation problem. In particular, for an matrix and , it computes a rank- approximation satisfying with high probability, in time . The analysis uses regularized spectral approximation to extend the approach of Chang and Yang (2026) from Gaussian to fast sparse sketches. The paper also provides guarantees for range finder and PSD Nyström approximation. Finally, the paper presents numerical experiments which demonstrates the advantage of the proposed algorithm.
Critical strengths
- The paper provides a unified analysis of sketched power methods with sparse sketches, establishing a flexible tradeoff between runtime and accuracy, and also extends this to some other problems. The technical contribution of this paper is solid.
- The paper gives an empirical evaluation of the proposed algorithms, demonstrating the practical advantage of the proposed algorithms, which is interesting to me.
Critical weaknesses
(Minor) The proposed algorithm is essentially the same as that of Chang and Yang (2026), so the main contribution of this paper is to extend the theoretical analysis to sparse sketches.
Questions for authors
- The main theorem in this paper is for an -rank approximation but not -rank. I am wondering whether this can be improved?
- It seems the proof in Appendix D can be simplified: for , we have . Substituting the spectral bound (3) and minimizing over directly gives (4)?
2 comments
Thanks to the authors for the response. I think my questions have been addressed, and it would be great if the authors could clarify those points in the final version.
Thank you for the feedback and suggestions.
Returning an exactly rank k approximation
This is a good question. Yes, in fact we can easily adapt the analysis to replace the O(k) rank with k by relying on a different low-rank approximation result for an exact rank k Gaussian sketch, e.g., Lemma 4 in Musco and Musco (2015). This will naturally slot into our analysis of the spectral norm bound in Theorem 3.5, in the place where we bound the norm under the 2q+11 exponent around line 393 in the manuscript. The reason we opted against doing this in the paper is that we wanted to provide a more modular and self-contained argument that only relies on the regularized spectral approximation property (otherwise, we would have to modify the condition 2 in the statement of Theorem 3.5). We will be sure to clarify this point in the final version.
Simplifying the proof
The proof can indeed be simplified in the manner described, thank you for pointing this out. We will add a remark to this effect in the final version but we think it may be worthwhile to keep the current proof to highlight the ideas about bounding the trace of the sketch-powered gram matrix along the singular directions of the original matrix.