acceptodds
Under review as a conference paper at ICLR 2027

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

Abstract

The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nystrom approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
matrix sketching, low-rank approximation, randomized numerical linear algebra

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rh53OpenReview ↗
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 n×nn \times n matrix AA and ℓ≥k\ell \ge k, it computes a rank-O(k)O(k) approximation A^\widehat{A} satisfying ∥A−A^∥22≤(1+ε)σk+12(A)+εℓ∑i>ℓσi2(A)\lVert A-\widehat{A}\rVert_2^2 \le (1+\varepsilon)\sigma_{k+1}^2(A) + \frac{\varepsilon}{\ell}\sum_{i>\ell}\sigma_i^2(A) with high probability, in time O~(nnz⁡(A)ε+nℓkε3)\widetilde{O}\left(\frac{\operatorname{nnz}(A)}{\varepsilon} + \frac{n\ell k}{\varepsilon^3}\right). 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 O(k)O(k)-rank approximation but not kk-rank. I am wondering whether this can be improved?
  • It seems the proof in Appendix D can be simplified: for R=(I−QQ⊤)AR=(I-QQ^\top)A, we have ∥R∥F2≤r∥R∥22+∑i>rσi2(A)\lVert R\rVert_F^2\le r\lVert R\rVert_2^2+\sum_{i>r}\sigma_i^2(A). Substituting the spectral bound (3) and minimizing over rr directly gives (4)?
2 comments

Thank you for the feedback and suggestions.

Returning an exactly rank kk approximation

This is a good question. Yes, in fact we can easily adapt the analysis to replace the O(k)O(k) rank with kk by relying on a different low-rank approximation result for an exact rank kk 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 12q+1\frac1{2q+1} 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.

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.

Reviewer_idd5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper focuses on low-rank matrix approximation and proposed an accelerating power method with fast sketching.

Critical strengths
  • Under a variety of fast sketching algorithms, detailed theoretical analysis was conducted for analyzing the effectiveness of the sketched power method.
  • It also showed how it can be used to improve the efficiency of standard tools for top-k SVD and low-rank factorization.
Critical weaknesses
  • Power method with sketching has been well studied in literature. The contribution of the manuscript seems incremental and lacks strong novelty.
  • The used key idea in Eqn (1) has been considered in Chang & Yang, 2026.
  • It is not clear how to set up the power q in practice. This is very important since the computation cost depends on it as well.
  • The experimental results are significantly insufficient, and no comparison to relevant existing methods (only classical RandSVD was considered).
  • The manuscript structure is strange. After Theorem 3.5 on page 6, the proofs of theorems 2.1, 2.3, and 3.5 are given, which is hard for the readers to follow.
Questions for authors

See above the weaknesses.

6 comments

Thank you for the feedback and comments. See the revised paper (Section 4 and Appendix E) for the updated experimental plots.

Comparison with Chang and Yang

It is true that Chang and Yang consider the same idea - in fact our two works arrived at this strategy independently and were released nearly concurrently on Arxiv. However, their work has a key limitation in that it relies very specifically on the rotational invariance properties of the Gaussian sketching matrix, which means that it could not be extended to fast sketching matrices. This is a crucial limitation since using a Gaussian matrix for the large intermediate sketch effectively eliminates any computational benefits of the sketched power method, because the O(nnz(A)l)O(nnz(A)l) cost of applying a Gaussian sketch of size l≫kl \gg k to the matrix is larger than the O~(nnz(A)k)\tilde{O}(nnz(A)k) cost of running the full power method in the first place. In Chang & Yang, this is justified by considering the storage benefits, since the sketch is still smaller than the original matrix. So while their work is indeed closely related to ours conceptually and algorithmically, their theoretical results do not provide any improvement over prior work in efficiently constructing a range finder or a low-rank factorization.

Setting power qq in practice

This is an interesting question (which also applies to classical RandSVD and other algorithms based on power iteration). Note that one can efficiently estimate the error at each iteration, and stop after the target error is reached. If the error is not reached with the current sketch size in a given time budget, we would then double the sketch size .

Experimental results and baselines

As mentioned in Section 4 of the original submission, we provided more experiments in Appendix E, which in particular included a comparison with another baseline, Generalized Nystrom. In this revision, we have done additional numerical experiments, including comparing against Randomized Block Krylov Iteration, as well as testing other rank parameters and sketch sparsities. See response to Reviewer mNFW and Figures 1, 2, 3, and 4 in the revised paper.

Manuscript structure

Our motivation behind putting the proof sketch of Theorem 3.5 at the end, after the proofs of Theorems 2.1 and 2.3, was that this is the most technical proof, and we thought it would help the reader to first understand how Theorem 3.5 can be used to obtain the main results from Section 2. We are open to revise this structure in the final version, if the reviewer thinks the readability can be improved this way.

Thanks for the responses and clarification. There are still some serious concerns:

  • The work of Chang & Yang was published in July 2026 in SIAM Journal on Matrix Analysis and Applications 47(3):1122-1165. DOI: 10.1137/25M1760143. As we know, the period of peer-review is quite long for a math journal. It might be not right to say the released date on arXiv is the time of the work; it could be when the work was accepted by SIAM and then the authors put it on arXiv. Moreover, I couldn't check your manuscript on arXiv since this will breach the double blind peer-review process.

  • Again, the comparison against baseline methods is very limited - there are many methods relevant to compare with regarding low-rank approximation.

Thank you for the clarification of the remaining concerns.

  • Regardless of the concurrency (which is difficult to establish), our work is still a meaningful improvement over Chang and Yang's results due to the fact that our results hold for sparse sketches, whereas in the case of dense Gaussian sketches as in Chang and Yang's work, one cannot obtain any computation time benefits over the standard power method.
  • We are now comparing to three different state-of-the-art baselines (RandSVD, RBKI, and Generalized Nystrom), and if the reviewer has another baseline in mind, we would be happy to include that as well in the final version.
Reviewer_mNFWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper focuses on theoretical analysis of "sketched power method" which is a variant of power method carried out with matrix sketches as opposed to original matrices. Rather than repeatedly applying the original matrix, the sketched power method first forms a smaller sketch ASAS, then performs power iterations with that sketch. To conduct theoretical analysis of this approach the authors develop a novel framework based on regularized spectral approximation property of fast sketching. The framework is applied to three tasks: constructing a range finder for randomized SVD, computing general low-rank factorizations, and factorizing positive-semidefinite matrices with a Nystrom method. The paper proves approximation-error and runtime bounds, including regimes where its method offers a stronger error guarantee than alternative approaches under a comparable computational budget. Experiments are presented on three benchmark matrices — smallnorb, ImageNet, and a synthetic matrix with polynomially decaying singular values. Experimental results suggest that the method reaches a useful approximation faster than classical randomized SVD, although its error eventually plateaus as sketch size limits the attainable accuracy.

Critical strengths
  • Novel theoretical analysis framework based on regularized spectral approximation property of fast sketches for studying sketched power method. The error and runtime bounds developed in the paper allow for informed selection of sketch sizes based on speed-accuracy tradeoffs.
  • In depth study of three related tasks under this framework: constructing a range finder matrix, low-rank factorization, and factorizing positive semidefinite matrices using the Nystrom method.
Critical weaknesses
  • Empirical study is limited; the main experiments cover three matrices and use a single target rank k=40k=40. Do the observed speed-accuracy gains hold across a broader range of ranks, sketches, and matrix structures?
  • With sketched power method there is an inherent approximation error that comes from using the sketch as opposed to original matrix. Have the authors considered approaches where over iterations the sketch also approaches the original matrix (possibly by increasing the rank of the sketch)?
  • The baseline comparison could be stronger. The presented experiment compares against classical randomized SVD. Krylov methods, one-pass sketch-power methods, and other sketch-based low-rank algorithms have different accuracy, memory, and data-pass trade-offs. Showing results with those approaches as other comparison points would be useful in further clarifying the proposed method's value.
Questions for authors

please see weaknesses above

2 comments

Thank you for the feedback and questions. See the revised paper (Section 4 and Appendix E) for the updated experimental plots.

Expanded empirical study

We have run additional experiments varying the target rank and sparsity. Considering additional ranks k=20 and k=80 for the imagenet matrix, we see similar efficiency-accuracy tradeoffs as in the case of k=40. In particular, for k=20, we see that Classical RandSVD takes on avg 0.04s to produce an avg relative error of 0.1 whereas Sketch-Powered RandSVD can get around 0.05 relative error in time ~0.03s (see Figure 3). Sketch-Powered RandSVD behaves similarly with increasing sparsity (See Figure 4) of the sketching matrix for 1, 3 and 5 nnz per column (for left sketches). In particular, the additional overhead due to sketching can be overcome by the gain from faster iterations till around 10 nnz per row/column. We have included these results in the revised paper in Figures 3, and 4 (Appendix E).

Additional baselines

For the comparison with one-pass methods, in our original submission (Figure 2, appendix E) we had already provided a numerical comparison of the performance of our Sketch-Powered Low-Rank Factorization (Algorithm 2 in the paper) with an extended version of the Generalized Nystrom algorithm (Nakatsukasa, 2020), which is a one pass method when q=0q=0. In the revised version we now also compare the performance of Sketch-Powered RandSVD with Randomized Block Krylov Iteration (RBKI, Musco and Musco, 2015). We observed that Sketch-Powered RandSVD is able to obtain a smaller relative error in the time it takes to run one iteration of RBKI. Of course, eventually RBKI achieves smaller error as Sketch-Powered RandSVD error saturates. For example, the following table (and revised Figure 1 in the paper) shows that on imagenet Sketch-Powered RandSVD reaches 0.1 relative error 36% faster than RBKI.

IterationMusco and Musco RBKI Time mean (s)Musco and Musco RBKI Error meanSketch-Powered RandSVD Time mean (s)Sketch-Powered RandSVD Error mean
00.0239054981.92826140.0274272611.9519617
10.0513779540.237714290.0309261660.34251246
20.0755851570.0138673460.0344271360.1984314
3——0.0379295810.15184105
4——0.0414325620.1266435
5——0.0449328460.11046064
6——0.0484331090.099146186
7——0.0519331430.091637328

Iteratively increasing sketches

We do believe that increasing the size of the sketch over iterations should lead to better approximation errors, and experimental data does suggest that the additional overhead of forming extra intermediate sketches would not be prohibitive. We had considered this approach, and it appears that obtaining the error analysis for this requires a substantial extension of our current theoretical framework, which is why we leave this to future work.

Dear Reviewer mNFW,

Did our rebuttal address all of your questions and concerns? We are happy to provide further clarifications during this discussion period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.