Sampling techniques for the Nyström method

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar

Research output: Contribution to journalConference articlepeer-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 distribution according to which columns are sampled from the original matrix. In this work, we present an analysis of different sampling techniques for the Nyström method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nyström method when used with uniform versus non-uniform sampling distributions. Our results suggest that uniform sampling without replacement, in addition to being more efficient both in time and space, produces more effective approximations. This motivates the theoretical part of our analysis which gives the first performance bounds for the Nyström method precisely when used with uniform sampling without replacement.

Original languageEnglish (US)
Pages (from-to)304-311
Number of pages8
JournalJournal of Machine Learning Research
StatePublished - 2009
Event12th International Conference on Artificial Intelligence and Statistics, AISTATS 2009 - Clearwater, FL, United States
Duration: Apr 16 2009Apr 18 2009

ASJC Scopus subject areas

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


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

Cite this