# A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2014.

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

- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifold](https://mlsanity.com/paper/2109.11196/) (2021)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [The Edge of Orthogonality: A Simple View of What Makes BYOL Tick](https://mlsanity.com/paper/2302.04817/) (2023)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Differentially private Riemannian optimization](https://mlsanity.com/paper/2205.09494/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Practical and Fast Momentum-Based Power Methods](https://mlsanity.com/paper/2108.09264/) (2021)
- [Universal Adversarial Directions](https://mlsanity.com/paper/2210.15997/) (2022)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flow](https://mlsanity.com/paper/2110.03273/) (2021)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

We describe and analyze a simple algorithm for principal component analysis and singular value decomposition, VR-PCA, which uses computationally cheap stochastic iterations, yet converges exponentially fast to the optimal solution. In contrast, existing algorithms suffer either from slow convergence, or computationally intensive iterations whose runtime scales with the data size. The algorithm builds on a recent variance-reduced stochastic gradient technique, which was previously analyzed for strongly convex optimization, whereas here we apply it to an inherently non-convex problem, using a very different analysis.