Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension
Manfred K. Warmuth, Dima Kuzmin · The MIT Press eBooks · 2007
We design an on-line algorithm for Principal Component Analysis. In each trial the current instance is projected onto a probabilistically chosen low dimen-sional subspace. The total expected quadratic approximation error equals the total quadratic approximation error of the best subspace chosen in hindsight plus some additional term that grows linearly in dimension of the subspace but logarithmi-cally in the dimension of the instances. 1