Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension
Warmuth, Manfred K., Kuzmin, Dima
–Neural Information Processing Systems
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 inthe dimension of the instances.
Neural Information Processing Systems
Dec-31-2007