Entrywise concentration bounds, a central limit theorem, and a median-of-means variance estimator give linear-time coordinate-wise uncertainty quantification for streaming PCA with Oja's algorithm.
Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We analyze Oja's algorithm for streaming $k$-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $d \times d$ symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top $k$ eigenvectors of their expectation using a number of samples that scales polylogarithmically with $d$. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.
fields
math.ST 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA
Entrywise concentration bounds, a central limit theorem, and a median-of-means variance estimator give linear-time coordinate-wise uncertainty quantification for streaming PCA with Oja's algorithm.