Timezone: »

Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #126
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

Author Information

Enayat Ullah (Johns Hopkins University)
Poorya Mianjy (Johns Hopkins University)
Teodor Vanislavov Marinov (Johns Hopkins University)
Raman Arora (Johns Hopkins University)

More from the Same Authors