# Memory Limited, Streaming PCA

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2013.

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

- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Differentially private and decentralized randomized power method](https://mlsanity.com/paper/2411.01931/) (2024)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [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)
- [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)
- [Practical and Fast Momentum-Based Power Methods](https://mlsanity.com/paper/2108.09264/) (2021)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [WARP: Weight Teleportation for Attack-Resilient Unlearning Protocols](https://mlsanity.com/paper/2512.00272/) (2025)
- [Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clustering](https://mlsanity.com/paper/2601.11626/) (2026)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flow](https://mlsanity.com/paper/2110.03273/) (2021)
- [Non-Volatile Memory Accelerated Geometric Multi-Scale Resolution Analysis](https://mlsanity.com/paper/2202.11518/) (2022)
- [Temporal Streaming Batch Principal Component Analysis for Time Series Classification](https://mlsanity.com/paper/2410.20820/) (2024)
- [PCA-VAE: Differentiable Subspace Quantization without Codebook Collapse](https://mlsanity.com/paper/2602.18904/) (2026)
- [Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation](https://mlsanity.com/paper/2605.09755/) (2026)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

We consider streaming, one-pass principal component analysis (PCA), in the high-dimensional regime, with limited memory. Here, p-dimensional samples are presented sequentially, and the goal is to produce the k-dimensional subspace that best approximates these points. Standard algorithms require O(p2) memory; meanwhile no algorithm can do better than O(kp) memory, since this is what the output itself requires. Memory (or storage) complexity is most meaningful when understood in the context of computational and sample complexity. Sample complexity for high-dimensional PCA is typically studied in the setting of the em spiked covariance model, where p-dimensional points are generated from a population covariance equal to the identity (white noise) plus a low-dimensional perturbation (the spike) which is the signal to be recovered. It is now well-understood that the spike can be recovered when the number of samples, n, scales proportionally with the dimension, p. Yet, all algorithms that provably achieve this, have memory complexity O(p2). Meanwhile, algorithms with memory-complexity O(kp) do not have provable bounds on sample complexity comparable to p. We present an algorithm that achieves both: it uses O(kp) memory (meaning storage of any kind) and is able to compute the k-dimensional spike with O(p log p) sample-complexity -- the first algorithm of its kind. While our theoretical analysis focuses on the spiked covariance model, our simulations show that our algorithm is successful on much more general models for the data.