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

De Huang, Jonathan Niles-Weed, Rachel Ward

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. $…