# Oja's Algorithm for Streaming Sparse PCA

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 64 references that are in the map.
- First posted on arXiv 11 Feb 2024.

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

- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [The Fast Convergence of Incremental PCA](https://mlsanity.com/paper/1501.03796/) (2015)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [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)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [History PCA: A New Algorithm for Streaming PCA](https://mlsanity.com/paper/1802.05447/) (2018)
- [Sparsistency and agnostic inference in sparse PCA](https://mlsanity.com/paper/1401.6978/) (2014)
- [Sparse PCA from Sparse Linear Regression](https://mlsanity.com/paper/1811.10106/) (2018)
- [Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1803.02312/) (2018)
- [Gradient-based Sparse Principal Component Analysis with Extensions to Online Learning](https://mlsanity.com/paper/1911.08048/) (2019)
- [Sparse principal component analysis and its l1-relaxation](https://mlsanity.com/paper/1712.00800/) (2017)
- [Support Recovery in Sparse PCA with Incomplete Data](https://mlsanity.com/paper/2205.15215/) (2022)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)

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

- [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)
- [Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics](https://mlsanity.com/paper/2512.01231/) (2025)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (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)
- [Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition](https://mlsanity.com/paper/2602.13759/) (2026)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)
- [SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA](https://mlsanity.com/paper/2609.26406/) (2026)

## Abstract (arXiv)

Oja's algorithm for Streaming Principal Component Analysis (PCA) for n data-points in a d dimensional space achieves the same sin-squared error O(r_mathsfeff/n) as the offline algorithm in O(d) space and O(nd) time and a single pass through the datapoints. Here r_mathsfeff is the effective rank (ratio of the trace and the principal eigenvalue of the population covariance matrix Sigma). Under this computational budget, we consider the problem of sparse PCA, where the principal eigenvector of Sigma is s-sparse, and r_mathsfeff can be large. In this setting, to our knowledge, textitthere are no known single-pass algorithms that achieve the minimax error bound in O(d) space and O(nd) time without either requiring strong initialization conditions or assuming further structure (e.g., spiked) of the covariance matrix. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm (the Oja vector) can achieve the minimax error bound under some regularity conditions in O(d) space and O(nd) time. We present a nontrivial and novel analysis of the entries of the unnormalized Oja vector, which involves the projection of a product of independent random matrices on a random initial vector. This is completely different from previous analyses of Oja's algorithm and matrix products, which have been done when the r_mathsfeff is bounded.