Streaming Kernel PCA with \(\tilde{O}(\sqrt{n})\) Random 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/\epsilon^2)\) sample complexity. Furthermore, we give a memory efficient streaming a...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-11
Main Authors: Ullah, Enayat, Mianjy, Poorya, Marinov, Teodor V, Arora, Raman
Format: Article
Language:English
Subjects:
Algorithms
Kernels
Principal components analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422