# LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

arXiv: https://arxiv.org/abs/1607.03463 · HTML: https://mlsanity.com/paper/1607.03463/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2016.

## Built on by (most cited first, 22 of 22)

- [Compression-aware Training of Neural Networks using Frank-Wolfe](https://mlsanity.com/paper/2205.11921/) (2022)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysis](https://mlsanity.com/paper/2402.09754/) (2024)
- [Half-Inverse Gradients for Physical Deep Learning](https://mlsanity.com/paper/2203.10131/) (2022)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [Efficient methods for Gaussian Markov random fields under sparse linear constraints](https://mlsanity.com/paper/2106.01712/) (2021)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Low-Rank Projections of GCNs Laplacian](https://mlsanity.com/paper/2106.07360/) (2021)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Mean of Means: A 10-dollar Solution for Human Localization with Calibration-free and Unconstrained Camera Settings](https://mlsanity.com/paper/2407.20870/) (2024)
- [Nash Equilibria via Stochastic Eigendecomposition](https://mlsanity.com/paper/2411.02308/) (2024)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)
- [Subspace Recovery in Winsorized PCA: Insights into Accuracy and Robustness](https://mlsanity.com/paper/2502.16391/) (2025)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)
- [Omnimodal Dataset Distillation via High-order Proxy Alignment](https://mlsanity.com/paper/2604.10666/) (2026)
- [Approximating Gaussian Whittle-Matern Fields over Well-Centered Triangulations of Riemannian Manifolds](https://mlsanity.com/paper/2606.13827/) (2026)

## Abstract (arXiv)

We study k-SVD that is to obtain the first k singular vectors of a matrix A. Recently, a few breakthroughs have been discovered on k-SVD: Musco and Musco [1] proved the first gap-free convergence result using the block Krylov method, Shamir [2] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [3] provided the fastest O(mathsfnnz(A) + mathsfpoly(1/varepsilon))-time algorithm using alternating minimization. In this paper, we put forward a new and simple LazySVD framework to improve the above breakthroughs. This framework leads to a faster gap-free method outperforming [1], and the first accelerated and stochastic method outperforming [2]. In the O(mathsfnnz(A) + mathsfpoly(1/varepsilon)) running-time regime, LazySVD outperforms [3] in certain parameter regimes without even using alternating minimization.