| |
Abstract:
We propose randomized techniques for speeding up Kernel
Principal Component Analysis on three levels: sampling and
quantization of the Gram matrix in training, randomized rounding
in evaluating the kernel expansions, and random projections in
evaluating the kernel itself. In all three cases, we give sharp
bounds on the accuracy of the obtained approximations. Rather
intriguingly, all three techniques can be viewed as
instantiations of the following idea: replace the kernel function
k
by a ``randomized kernel'' which behaves like
k
in expectation.
|
