We study the statistical and computational aspects of kernel principal component analysis using random Fourier features and show that under mild assumptions, O(√n log (n)) features suffice to achieve O(1/ε^2) sample complexity. Further- more, we give a memory efficient streaming algorithm based on classical Oja’s algorithm that achieves this rate.