Title: 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.