mlsanityData to 14 Oct 2026

First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate

arXiv 1607.07837 ↗First posted 26 Jul 2016math.OC cs.DS cs.LGcited by 32

Not on the map. Why?

Abstract (arXiv)

We study streaming principal component analysis (PCA), that is to find, in O(dk) space, the top k eigenvectors of a d× d hidden matrix bf Sigma with online vectors drawn from covariance matrix bf Sigma. We provide textitglobal convergence for Oja's algorithm which is popularly used in practice but lacks theoretical understanding for k>1. We also provide a modified variant mathsfOja++ that runs textiteven faster than Oja's. Our results match the information theoretic lower bound in terms of dependency on error, on eigengap, on rank k, and on dimension d, up to poly-log factors. In addition, our convergence rate can be made gap-free, that is proportional to the approximation error and independent of the eigengap. In contrast, for general rank k, before our work (1) it was open to design any algorithm with efficient global convergence rate; and (2) it was open to design any algorithm with (even local) gap-free convergence rate in O(dk) space.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 Jul 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 5; 2024: 4; 2025: 5; 2026: 9.

32 papers.

Sort:

  1. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  2. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  3. 2021EigenGame Unloaded: When playing games is better than optimizingcited by 13
  4. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  5. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  6. 2023Streaming PCA for Markovian Datacited by 9
  7. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  8. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  9. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  10. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 3
  11. 2025Low-Precision Streaming PCAcited by 3
  12. 2021Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problemscited by 2
20 more
  1. 2022An online algorithm for contrastive Principal Component Analysiscited by 2
  2. 2023The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learningcited by 2
  3. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  4. 2023On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysiscited by 1
  5. 2025Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflationcited by 1
  6. 2026TTQ: Activation-Aware Test-Time Quantization to Accelerate LLM Inference On The Flycited by 1
  7. 2026History-aware adaptive reduced-order models via incremental singular value decompositioncited by 1
  8. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  9. 2022Self-consistent Gradient-like Eigen Decomposition in Solving Schr"odinger Equationscited by 0
  10. 2022The Symmetric Generalized Eigenvalue Problem as a Nash Equilibriumcited by 0
  11. 2022Stochastic Parallelizable Eigengap Dilation for Large Graph Clusteringcited by 0
  12. 2024Nash Equilibria via Stochastic Eigendecompositioncited by 0
  13. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  14. 2025Global Convergence of Adaptive Sensing for Principal Eigenvector Estimationcited by 0
  15. 2026Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecompositioncited by 0
  16. 2026Factor Augmented High-Dimensional SGDcited by 0
  17. 2026Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computationcited by 0
  18. 2026Inference and Uncertainty Quantification for Streaming r-PCAcited by 0
  19. 2026Gap-free Differentially Private PCA for Gaussian Datacited by 0
  20. 2026AIM-ZO: Activation-Informed Subspace Maintenance for Zeroth-Order LLM Fine-Tuningcited by 0