Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates

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.

arXiv comment28 pages

References in corpus (7)

• The Noisy Power Method: A Meta Algorithm with Applications
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
• The Fast Convergence of Incremental PCA
• AdaOja: Adaptive Learning Rates for Streaming PCA
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Matrix Concentration for Products

Cited by in corpus (1)

• On the Correspondence between Gaussian Processes and Geometric Harmonics