Randomized Online PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension
Abstract
We design an online algorithm for Principal Component Analysis. In each trial the current instance is centered and projected into a probabilistically chosen low dimensional subspace. The regret of our online algorithm, that is, the total expected quadratic compression loss of the online algorithm minus the total quadratic compression loss of the batch algorithm, is bounded by a term whose dependence on the dimension of the instances is only logarithmic.
Cite
Text
Warmuth and Kuzmin. "Randomized Online PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension." Journal of Machine Learning Research, 2008.Markdown
[Warmuth and Kuzmin. "Randomized Online PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension." Journal of Machine Learning Research, 2008.](https://mlanthology.org/jmlr/2008/warmuth2008jmlr-randomized/)BibTeX
@article{warmuth2008jmlr-randomized,
title = {{Randomized Online PCA Algorithms with Regret Bounds That Are Logarithmic in the Dimension}},
author = {Warmuth, Manfred K. and Kuzmin, Dima},
journal = {Journal of Machine Learning Research},
year = {2008},
pages = {2287-2320},
volume = {9},
url = {https://mlanthology.org/jmlr/2008/warmuth2008jmlr-randomized/}
}