Abstract
We study the statistical and computational aspects of kernel principal component analysis ? using random Fourier features and show that under mild assumptions, features suffice to achieve sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja’s algorithm that achieves this rate.