EUVIMEDEUVIMED entdecken
Crossref

Improving Sketching Algorithms for Low-Rank Matrix Approximation via Sketch-Power Iterations

Chao Chang, Yuning Yang

SIAM Journal on Matrix Analysis and Applications · 30.09.2026 · 47 (3) · 1122-1165

DOI: 10.1137/25m1760143 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 10.07.2026. Verfasst von Chao Chang und 1 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben. Gefördert von: Guangxi Ba Gui Scholars Foundation, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Power iteration can improve the accuracy of randomized SVD, but requires multiple data passes, making it impractical in streaming or memory-constrained settings. We introduce a lightweight yet effective sketch-power iteration, allowing power-like iterations with only a single pass of the data, which can be incorporated into one-pass algorithms for low-rank approximation. As an example, we integrate the sketch-power iteration into a one-pass algorithm proposed by Tropp et al., and introduce strategies to reduce its storage cost. We establish meaningful error bounds: given a fixed storage budget, the sketch sizes derived from the bounds closely match the optimal ones observed in reality. This allows one to preselect reasonable parameters. Numerical experiments on both synthetic and real-world datasets indicate that, under the same storage constraints, applying one or two sketch-power iterations can substantially improve the approximation accuracy of the considered one-pass algorithms. In particular, experiments on real data with flat spectrum show that the method can approximate the dominant singular vectors well. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/Mitchell-Cxyk/SketchPowerIteration and in the supplementary materials ( Supp_Materials_1.pdf [431KB], Supp_Materials_2.zip [17.3MB]). [Formula: see text]

Förderung

  • Guangxi Ba Gui Scholars Foundation
  • National Natural Science Foundation of China

Zitieren

APA

Chang, C., & Yang, Y. (2026). Improving Sketching Algorithms for Low-Rank Matrix Approximation via Sketch-Power Iterations. SIAM Journal on Matrix Analysis and Applications, 47(3), 1122-1165. https://doi.org/10.1137/25m1760143

Vancouver

Chang C, Yang Y. Improving Sketching Algorithms for Low-Rank Matrix Approximation via Sketch-Power Iterations. SIAM Journal on Matrix Analysis and Applications. 2026;47(3):1122-1165. doi:10.1137/25m1760143

BibTeX
@article{Chang2026,
  author = {Chang, Chao and Yang, Yuning},
  title = {Improving Sketching Algorithms for Low-Rank Matrix Approximation via Sketch-Power Iterations},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  year = {2026},
  volume = {47},
  number = {3},
  pages = {1122--1165},
  doi = {10.1137/25m1760143}
}
Kostenlos starten →