Kernel Principal Component Analysis (KPCA) is a relatively new machine learning technique that significantly generalizes PCA. While effective, KPCA scales very poorly to large data sets as it requires the eigendecomposition of a correspondingly large, dense matrix. We show how one can employ randomization to dramatically speed up KPCA by employing three orthogonal techniques: i) sampling and quantizing the entries of the Gram matrix, ii) applying randomized rounding in evaluating them kernel expansions, and iii) using random projections in evaluating the kernel itself. In all three cases, we give sharp, high-probability bounds on the accuracy of the obtained results.
Interestingly, it seems that all three of these techniques can be cast as instantiations of the following very simple idea: replace the kernel function k by some "randomized kernel function" that behaves like k in expectation. The central limit theorem, in different guises, does all the remaining work.
Based on joint work with Frank McSherry (UW) and Bernhard Scholkopf (Max Planck).