# Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2016.

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

- [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)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [The Edge of Orthogonality: A Simple View of What Makes BYOL Tick](https://mlsanity.com/paper/2302.04817/) (2023)
- [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)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [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)
- [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)
- [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)
- [Kolmogorov-Arnold Attention: Is Learnable Attention Better For Vision Transformers?](https://mlsanity.com/paper/2503.10632/) (2025)
- [Practical and Fast Momentum-Based Power Methods](https://mlsanity.com/paper/2108.09264/) (2021)
- [On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis](https://mlsanity.com/paper/2310.04283/) (2023)
- [Adaptive Power Iteration Method for Differentially Private PCA](https://mlsanity.com/paper/2602.11454/) (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)
- [Minimal Communication-Cost Statistical Learning](https://mlsanity.com/paper/2406.08193/) (2024)
- [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)
- [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)

This work provides improved guarantees for streaming principle component analysis (PCA). Given A1, ldots, An∈ ℝd× d sampled independently from distributions satisfying mathbbE[Ai] = Sigma for Sigma succeq 0, this work provides an O(d)-space linear-time single-pass streaming algorithm for estimating the top eigenvector of Sigma. The algorithm nearly matches (and in certain cases improves upon) the accuracy obtained by the standard batch method that computes top eigenvector of the empirical covariance frac1n sumi ∈ [n] Ai as analyzed by the matrix Bernstein inequality. Moreover, to achieve constant accuracy, our algorithm improves upon the best previous known sample complexities of streaming algorithms by either a multiplicative factor of O(d) or 1/gap where gap is the relative distance between the top two eigenvalues of Sigma. These results are achieved through a novel analysis of the classic Oja's algorithm, one of the oldest and most popular algorithms for streaming PCA. In particular, this work shows that simply picking a random initial point w0 and applying the update rule wi + 1 = wi + ηi Ai wi suffices to accurately estimate the top eigenvector, with a suitable choice of ηi. We believe our result sheds light on how to efficiently perform streaming PCA both in theory and in practice and we hope that our analysis may serve as the basis for analyzing many variants and extensions of streaming PCA.