|
Abstract : |
A major problem for kernel-based predictors (such as Support Vector Machines and Gaussian processes) is that the amount of computation required to nd the solution scales as O(n 3), where n is the number of training examples. We show that an approximation to the eigendecomposition of the Gram matrix can be computed by the Nystrom method (which is used for the numerical solution of eigenproblems). This is achieved by carrying out an eigendecomposition on a smaller system of size m n, and then expanding the results back up to n dimensions. The computational complexity of a predictor using this approximation is O(m 2, |
