# Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 6 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Memory Limited, Streaming PCA](https://mlsanity.com/paper/1307.0032/) (2013)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [The Fast Convergence of Incremental PCA](https://mlsanity.com/paper/1501.03796/) (2015)
- [Near-Optimal Stochastic Approximation for Online Principal Component Estimation](https://mlsanity.com/paper/1603.05305/) (2016)
- [Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law](https://mlsanity.com/paper/1804.01221/) (2018)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity](https://mlsanity.com/paper/1507.08788/) (2015)
- [Online Algorithms for Factorization-Based Structure from Motion](https://mlsanity.com/paper/1309.6964/) (2013)
- [Finding the largest low-rank clusters with Ky Fan 2-k-norm and ℓ1-norm](https://mlsanity.com/paper/1403.5901/) (2014)
- [Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA](https://mlsanity.com/paper/1506.01490/) (2015)

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

- [Preference Dynamics Under Personalized Recommendations](https://mlsanity.com/paper/2205.13026/) (2022)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (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)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [On the Correspondence between Gaussian Processes and Geometric Harmonics](https://mlsanity.com/paper/2110.02296/) (2021)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guarantees](https://mlsanity.com/paper/2411.07120/) (2024)
- [Graph Regularized PCA](https://mlsanity.com/paper/2601.10199/) (2026)
- [Pro-KLShampoo: Projected KL-Shampoo with Whitening Recovered by Orthogonalization](https://mlsanity.com/paper/2605.06316/) (2026)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Spike-timing-dependent Hebbian learning as noisy gradient descent](https://mlsanity.com/paper/2505.10272/) (2025)
- [Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation](https://mlsanity.com/paper/2505.10882/) (2025)
- [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)
- [AIM-ZO: Activation-Informed Subspace Maintenance for Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2609.35257/) (2026)

## Abstract (arXiv)

We analyze Oja's algorithm for streaming k-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. d × d symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top k eigenvectors of their expectation using a number of samples that scales polylogarithmically with d. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.