Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension

Part of Advances in Neural Information Processing Systems 19 (NIPS 2006)

Authors

Manfred K. K. Warmuth, Dima Kuzmin

Abstract

We design an on-line algorithm for Principal Component Analysis. In each trial the current instance is projected onto a probabilistically chosen low dimensional 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 logarithmically in the dimension of the instances.