mlsanityData to 7 Oct 2026

LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

arXiv 1607.03463 ↗First posted 12 Jul 2016math.NA cs.DS cs.LGcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 1; 2024: 5; 2025: 4; 2026: 4.

22 papers.

Sort:

  1. 2022Compression-aware Training of Neural Networks using Frank-Wolfecited by 16
  2. 2022A Robust Spectral Algorithm for Overcomplete Tensor Decompositioncited by 7
  3. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  4. 2022Fast algorithm for overcomplete order-3 tensor decompositioncited by 5
  5. 2021FedPower: Privacy-Preserving Distributed Eigenspace Estimationcited by 4
  6. 2024Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysiscited by 4
  7. 2022Half-Inverse Gradients for Physical Deep Learningcited by 3
  8. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  9. 2021Efficient methods for Gaussian Markov random fields under sparse linear constraintscited by 1
  10. 2023Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementaritycited by 1
  11. 2024Decentralized Sum-of-Nonconvex Optimizationcited by 1
  12. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
10 more
  1. 2021Low-Rank Projections of GCNs Laplaciancited by 0
  2. 2022Improved analysis of randomized SVD for top-eigenvector approximationcited by 0
  3. 2024Mean of Means: A 10-dollar Solution for Human Localization with Calibration-free and Unconstrained Camera Settingscited by 0
  4. 2024Nash Equilibria via Stochastic Eigendecompositioncited by 0
  5. 2025k-SVD with Gradient Descentcited by 0
  6. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  7. 2025Subspace Recovery in Winsorized PCA: Insights into Accuracy and Robustnesscited by 0
  8. 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0
  9. 2026Omnimodal Dataset Distillation via High-order Proxy Alignmentcited by 0
  10. 2026Approximating Gaussian Whittle-Matern Fields over Well-Centered Triangulations of Riemannian Manifoldscited by 0