Ensemble nyström

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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
Pages203-223
Number of pages21
ISBN (Electronic)9781441993267
ISBN (Print)9781441993250
DOIs
StatePublished - Jan 1 2012

ASJC Scopus subject areas

  • Computer Science(all)

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

Cite this