Subspace sampling and relative-error matrix approximation: Column-based methods

Petros Drineas, Michael W. Mahoney, S. Muthukrishnan

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

    Abstract

    Given an m × n matrix A and an integer k less than the rank of A, the "best" rank k approximation to A that minimizes the error with respect to the Frobenius norm is Ak, which is obtained by projecting A on the top k left singular vectors of A. While Ak is routinely used in data analysis, it is difficult to interpret and understand it in terms of the original data, namely the columns and rows of A. For example, these columns and rows often come from some application domain, whereas the singular vectors are linear combinations of (up to all) the columns or rows of A. We address the problem of obtaining low-rank approximations that are directly interpretable in terms of the original columns or rows of A. Our main results are two polynomial time randomized algorithms that take as input a matrix A and return as output a matrix C, consisting of a "small" (i.e., a low-degree polynomial in k, 1/ε;, and log(1/δ)) number of actual columns of A such that ||A - CC+A||F ≤ (1 + ε) ||A - Ak|| F with probability at least 1 - δ. Our algorithms are simple, and they take time of the order of the time needed to compute the top k right singular vectors of A. In addition, they sample the columns of A via the method of "subspace sampling," so-named since the sampling probabilities depend on the lengths of the rows of the top singular vectors and since they ensure that we capture entirely a certain subspace of interest.

    Original languageEnglish (US)
    Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
    PublisherSpringer Verlag
    Pages316-326
    Number of pages11
    ISBN (Print)3540380442, 9783540380443
    DOIs
    StatePublished - 2006
    Event9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain
    Duration: Aug 28 2006Aug 30 2006

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4110 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
    CountrySpain
    CityBarcelona
    Period8/28/068/30/06

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Subspace sampling and relative-error matrix approximation: Column-based methods'. Together they form a unique fingerprint.

  • Cite this

    Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2006). Subspace sampling and relative-error matrix approximation: Column-based methods. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a (pp. 316-326). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4110 LNCS). Springer Verlag. https://doi.org/10.1007/11830924_30