Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
Abstract
We study the statistical and computational aspects of kernel principal component analysis using random Fourier features and show that under mild assumptions, $O(\sqrt{n} \log n)$ features suffices to achieve $O(1/\epsilon^2)$ sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja's algorithm that achieves this rate
Cite
Text
Ullah et al. "Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features." Neural Information Processing Systems, 2018.Markdown
[Ullah et al. "Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/ullah2018neurips-streaming/)BibTeX
@inproceedings{ullah2018neurips-streaming,
title = {{Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features}},
author = {Ullah, Enayat and Mianjy, Poorya and Marinov, Teodor Vanislavov and Arora, Raman},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {7311-7321},
url = {https://mlanthology.org/neurips/2018/ullah2018neurips-streaming/}
}