Robust Streaming PCA
stat.ML, cs.LG
Submitted: 2019-02-08
Updated: 2026-09-02
Comments: The authors are ordered alphabetically. 36th Conference on Neural Information Processing Systems (NeurIPS 2022). This version corrects several steps in the proofs, expands the appendices, and revises the exposition throughout
License: http://creativecommons.org/licenses/by/4.0/
The gist: We consider streaming principal component analysis when the stochastic data generating model is subject to perturbations.
Terminology
Abstract
We consider streaming principal component analysis when the stochastic data generating model is subject to perturbations. While existing models assume a fixed covariance, we adopt a robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits on convergence of any algorithm recovering principal components. We analyze the convergence of the noisy power method and Oja's algorithm, both studied for the stationary data generating model, and argue that the noisy power method is rate-optimal in our setting. Finally, we demonstrate the validity of our analysis through numerical experiments on synthetic and real-world datasets.
Sources
- Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
- Online Robust Subspace Tracking from Partial Information
- Matrix Concentration for Products
- On the Optimality of the Oja's Algorithm for Online PCA
- History PCA: A New Algorithm for Streaming PCA
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Efficient quadratic entropy with distance sketches
- Embedding-Bias in Conditional Independence Testing
- From Log-Odds to Shapley Values: An Explanatory Geometry for the Weighted Naive Bayes Classifier