Sampling methods for the Nyström method

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar

Research output: Contribution to journalArticlepeer-review


The Nyström method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the procedure according to which columns are sampled from the original matrix. In this work, we explore the efficacy of a variety of fixed and adaptive sampling schemes. We also propose a family of ensemble- based sampling algorithms for the Nyström method. We report results of extensive experiments that provide a detailed comparison of various fixed and adaptive sampling techniques, and demonstrate the performance improvement associated with the ensemble Nyström method when used in conjunction with either fixed or adaptive sampling schemes. Corroborating these empirical findings, we present a theoretical analysis of the Nyström method, providing novel error bounds guaranteeing a better convergence rate of the ensemble Nyström method in comparison to the standard Nyström method.

Original languageEnglish (US)
Pages (from-to)981-1006
Number of pages26
JournalJournal of Machine Learning Research
StatePublished - Apr 2012


  • Ensemble methods
  • Large-scale learning
  • Low-rank approximation
  • Nyström method

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Sampling methods for the Nyström method'. Together they form a unique fingerprint.

Cite this