# First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate

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

## Key facts

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

## Built on by (most cited first, 30 of 32)

- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [An online algorithm for contrastive Principal Component Analysis](https://mlsanity.com/paper/2211.07723/) (2022)
- [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis](https://mlsanity.com/paper/2310.04283/) (2023)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [TTQ: Activation-Aware Test-Time Quantization to Accelerate LLM Inference On The Fly](https://mlsanity.com/paper/2603.19296/) (2026)
- [History-aware adaptive reduced-order models via incremental singular value decomposition](https://mlsanity.com/paper/2605.28684/) (2026)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Self-consistent Gradient-like Eigen Decomposition in Solving Schr"odinger Equations](https://mlsanity.com/paper/2202.01388/) (2022)
- [The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium](https://mlsanity.com/paper/2206.04993/) (2022)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [Nash Equilibria via Stochastic Eigendecomposition](https://mlsanity.com/paper/2411.02308/) (2024)
- [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)
- [Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation](https://mlsanity.com/paper/2505.10882/) (2025)
- [Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition](https://mlsanity.com/paper/2602.13759/) (2026)
- [Factor Augmented High-Dimensional SGD](https://mlsanity.com/paper/2605.19291/) (2026)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)
- [Inference and Uncertainty Quantification for Streaming r-PCA](https://mlsanity.com/paper/2608.18374/) (2026)

## Abstract (arXiv)

We study streaming principal component analysis (PCA), that is to find, in O(dk) space, the top k eigenvectors of a d× d hidden matrix bf Sigma with online vectors drawn from covariance matrix bf Sigma. We provide textitglobal convergence for Oja's algorithm which is popularly used in practice but lacks theoretical understanding for k>1. We also provide a modified variant mathsfOja++ that runs textiteven faster than Oja's. Our results match the information theoretic lower bound in terms of dependency on error, on eigengap, on rank k, and on dimension d, up to poly-log factors. In addition, our convergence rate can be made gap-free, that is proportional to the approximation error and independent of the eigengap. In contrast, for general rank k, before our work (1) it was open to design any algorithm with efficient global convergence rate; and (2) it was open to design any algorithm with (even local) gap-free convergence rate in O(dk) space.