Sampling Techniques for Kernel Methods
Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf · The MIT Press eBooks · 2002
We propose sampling methods for speeding up kernel techniques on three levels. We sparsify the Gram matrix, the kernel expansion, and, for a class of commonly used kernels, we propose a sampling approach to the evaluation of the kernel function itself. In all three cases, we give sharp bounds on the accuracy of the obtained approximations.