On sampling-based approximate spectral decomposition

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper addresses the problem of approximate singular value decomposition of large dense matrices that arises naturally in many machine learning applications. We discuss two recently introduced sampling-based spectral decomposition techniques: the Nyström and the Column-sampling methods. We present a theoretical comparison between the two methods and provide novel insights regarding their suitability for various applications. We then provide experimental results motivated by this theory. Finally, we propose an efficient adaptive sampling technique to select informative columns from the original matrix. This novel technique outperforms standard sampling methods on a variety of datasets.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th International Conference On Machine Learning, ICML 2009
Pages553-560
Number of pages8
StatePublished - 2009
Event26th International Conference On Machine Learning, ICML 2009 - Montreal, QC, Canada
Duration: Jun 14 2009Jun 18 2009

Publication series

NameProceedings of the 26th International Conference On Machine Learning, ICML 2009

Other

Other26th International Conference On Machine Learning, ICML 2009
CountryCanada
CityMontreal, QC
Period6/14/096/18/09

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'On sampling-based approximate spectral decomposition'. Together they form a unique fingerprint.

  • Cite this

    Kumar, S., Mohri, M., & Talwalkar, A. (2009). On sampling-based approximate spectral decomposition. In Proceedings of the 26th International Conference On Machine Learning, ICML 2009 (pp. 553-560). (Proceedings of the 26th International Conference On Machine Learning, ICML 2009).