# Spectral Guarantees for Adversarial Streaming PCA

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 19 Aug 2024.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [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)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [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)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [The Fast Convergence of Incremental PCA](https://mlsanity.com/paper/1501.03796/) (2015)
- [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)
- [Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings](https://mlsanity.com/paper/2202.09797/) (2022)
- [The Price of Differential Privacy for Low-Rank Factorization](https://mlsanity.com/paper/1604.01429/) (2016)

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

- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)

## Abstract (arXiv)

In streaming PCA, we see a stream of vectors x1, dotsc, xn ∈ ℝd and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral ratio R = λ1 / λ2 is large. We ask: how large does R need to be to solve streaming PCA in widetildeO(d) space? Existing algorithms require R = widetildeOmega(d). We show: (1) For all mergeable summaries, R = widetildeOmega(√d) is necessary. (2) In the insertion-only model, a variant of Oja's algorithm gets o(1) error for R = O(log n log d). (3) No algorithm with o(d2) space gets o(1) error for R = O(1). Our analysis is the first application of Oja's algorithm to adversarial streams. It is also the first algorithm for adversarial streaming PCA that is designed for a spectral, rather than Frobenius, bound on the tail; and the bound it needs is exponentially better than is possible by adapting a Frobenius guarantee.