Randomized PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension
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.
Cite
Text
Warmuth and Kuzmin. "Randomized PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension." Neural Information Processing Systems, 2006.Markdown
[Warmuth and Kuzmin. "Randomized PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension." Neural Information Processing Systems, 2006.](https://mlanthology.org/neurips/2006/warmuth2006neurips-randomized/)BibTeX
@inproceedings{warmuth2006neurips-randomized,
title = {{Randomized PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension}},
author = {Warmuth, Manfred K. and Kuzmin, Dima},
booktitle = {Neural Information Processing Systems},
year = {2006},
pages = {1481-1488},
url = {https://mlanthology.org/neurips/2006/warmuth2006neurips-randomized/}
}