Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Using the Nystroem Method to Speed Up Kernel Machines
Authors: Chris Williams ; Matthias Seeger
Date: 2001
Publication Title:Advances in Neural Information Processing Systems 13
Publisher:MIT Press
Publication Type:Conference Paper Publication Status:Published
Page Nos:682-688
A major problem for kernel-based predictors (such as Support Vector Machines and Gaussian processes) is that the amount of computation required to find 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 Nystroem 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 n). We report experiments on the USPS and abalone data sets and show that we can set m << n without any significant decrease in the accuracy of the solution.
Links To Paper
Author's publications page
NIPS online publilcations repository
Bibtex format
author = { Chris Williams and Matthias Seeger },
title = {Using the Nystroem Method to Speed Up Kernel Machines},
book title = {Advances in Neural Information Processing Systems 13},
publisher = {MIT Press},
year = 2001,
pages = {682-688},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh