Deterministic column sampling for low-rank matrix approximation: Nyström vs. Incomplete Cholesky decomposition

Raajen Patel, Tom Goldstein, Eva Dyer, Azalia Mirhoseini, Richard Baraniuk

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

2 Scopus citations

Abstract

Kernel matrices that encode the distance (or similarity) between data points are widely used throughout the computational sciences for classification, clustering, and dimensionality reduction. For large datasets, the cost of computing and factorizing such matrices becomes intractable. Thus instead of operating on the entire matrix, approximate methods such as the Nystrom method and the incomplete Cholesky decomposition (ICD) generate a low rank matrix factorization using only a subset of the matrix columns (or rows). Here, we present an adaptive column sampling strategy for the Nystrom method that we dub Accelerated Sequential Incoherence Selection (oASIS). This sampling strategy reveals a missing link between Nystrom methods and ICD: we demonstrate that ICD is actually a special case of the Nystrom method with the oASIS adaptive sampling rule. Numerical experiments and theoretical results suggest that oASIS achieves performance comparable to state-of-the-art greedy Nystrom methods but with shorter runtimes and less memory consumption.

Original languageEnglish (US)
Title of host publication16th SIAM International Conference on Data Mining 2016, SDM 2016
EditorsSanjay Chawla Venkatasubramanian, Wagner Meira
PublisherSociety for Industrial and Applied Mathematics Publications
Pages594-602
Number of pages9
ISBN (Electronic)9781510828117
DOIs
StatePublished - 2016
Event16th SIAM International Conference on Data Mining 2016, SDM 2016 - Miami, United States
Duration: May 5 2016May 7 2016

Publication series

Name16th SIAM International Conference on Data Mining 2016, SDM 2016

Other

Other16th SIAM International Conference on Data Mining 2016, SDM 2016
CountryUnited States
CityMiami
Period5/5/165/7/16

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Fingerprint Dive into the research topics of 'Deterministic column sampling for low-rank matrix approximation: Nyström vs. Incomplete Cholesky decomposition'. Together they form a unique fingerprint.

Cite this