Spectral Guarantees for Adversarial Streaming PCA
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 16 of its 33 references that are in the map. First posted on arXiv 19 Aug 2024.
Builds on
16 of 33 references.
References · 16
- 2014Sketching as a Tool for Numerical Linear Algebracited by 285
- 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
- 2021Instance-Optimal Compressed Sensing via Posterior Samplingcited by 43
- 2015Frequent Directions : Simple and Deterministic Matrix Sketchingcited by 39
- 2016Practical sketching algorithms for low-rank matrix approximationcited by 38
- 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
- 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
- 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
- 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
- 2013Memory Limited, Streaming PCAcited by 21
- 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
- 2015The Fast Convergence of Incremental PCAcited by 15
4 more
- 2021Bootstrapping the error of Oja's algorithmcited by 11
- 2023Streaming PCA for Markovian Datacited by 9
- 2022Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddingscited by 4
- 2016The Price of Differential Privacy for Low-Rank Factorizationcited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.