Using the Nyström Method to Speed Up Kernel Machines

by Christopher K. I. Willians and Matthias Seeger

This is an old paper, which I must scan for recent research. The Nyström method originates from the numerical solution of integral equations. Since in kernel methods, we have to eigen decompose a large Gram matrix (of size N, the number of samples), which requires O( N3 ).

The eigen decomposition yields the basis functions evaluating at the sample points and the eigenvalues, which could be used to approximate the basis functions evaluating at an arbitrary position. This is the so-called Nyström method. What this paper says is to select randomly a subset of the samples, for which the required elements in Nyström method are derived. As is written in the paper, only comparatively small amount of calculation needs to be done.

This technique is verified on Gaussian Process in the experiment, yielding a good approximation.