Ensemble nyström

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar

Research output: Chapter in Book/Report/Conference proceedingChapter


A crucial technique for scaling kernel methods to very large datasets reaching or exceeding millions of instances is based on low-rank approximation of kernel matrices. The Nyström method is a popular technique to generate low-rank matrix approximations but it requires sampling of a large number of columns from the original matrix to achieve good accuracy. This chapter describes a new family of algorithms based on mixtures of Nyström approximations, Ensemble Nyström algorithms, that yield more accurate low-rank approximations than the standard Nyström method. We give a detailed study of variants of these algorithms based on simple averaging, an exponential weight method, and regression-based methods. A theoretical analysis of these algorithms, including novel error bounds guaranteeing a better convergence rate than the standard Nyström method is also presented. Finally, experiments with several datasets containing up to 1 M points are presented, demonstrating significant improvement over the standard Nyström approximation.

Original languageEnglish (US)
Title of host publicationEnsemble Machine Learning
Subtitle of host publicationMethods and Applications
PublisherSpringer US
Number of pages21
ISBN (Electronic)9781441993267
ISBN (Print)9781441993250
StatePublished - Jan 1 2012

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Ensemble nyström'. Together they form a unique fingerprint.

Cite this