# Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2015.

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

- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysis](https://mlsanity.com/paper/2402.09754/) (2024)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [Quantum principal component analysis without eigenvector recovery](https://mlsanity.com/paper/2605.27942/) (2026)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

We study the convergence properties of the VR-PCA algorithm introduced by citeshamir2015stochastic for fast computation of leading singular vectors. We prove several new results, including a formal analysis of a block version of the algorithm, and convergence from random initialization. We also make a few observations of independent interest, such as how pre-initializing with just a single exact power iteration can significantly improve the runtime of stochastic methods, and what are the convexity and non-convexity properties of the underlying optimization problem.