Input sparsity time low-rank approximation via ridge leverage score sampling

Christopher Musco, Michael B. Cohen, Cameron Musco

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

29 Scopus citations

Abstract

We present a new algorithm for finding a near optimal low-rank approximation of a matrix A in O(nnz(A)) time. Our method is based on a recursive sampling scheme for computing a representative subset of A's columns, which is then used to find a low-rank approximation. This approach differs substantially from prior O(nnz(A)) time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. Our algorithm matches the guarantees of the random projection methods while offering a number of advantages. In addition to better performance on sparse and structured data, sampling algorithms can be applied in settings where random projections cannot. For example, we give new streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used in the fastest algorithms for provably accurate Nystrom approximation of kernel matrices [56].

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages1758-1777
Number of pages20
ISBN (Electronic)9781611974782
DOIs
StatePublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Input sparsity time low-rank approximation via ridge leverage score sampling'. Together they form a unique fingerprint.

  • Cite this

    Musco, C., Cohen, M. B., & Musco, C. (2017). Input sparsity time low-rank approximation via ridge leverage score sampling. In P. N. Klein (Ed.), 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1758-1777). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 0). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974782.115