Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
This work addresses efficiency challenges in kernel PCA for large-scale or streaming data applications, representing an incremental improvement over existing methods.
The paper tackles the problem of reducing computational and memory costs in kernel principal component analysis by proposing a streaming algorithm that uses random Fourier features, achieving O(1/ε²) sample complexity with O(√n log n) features.
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/ε^2)$ sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja's algorithm that achieves this rate.