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

    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

    Conference

    Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
    Country/TerritorySpain
    CityBarcelona
    Period1/16/171/19/17

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    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