Uniform sampling for matrix approximation

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford

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

44 Scopus citations

Abstract

Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances. We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation. This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.

Original languageEnglish (US)
Title of host publicationITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages181-190
Number of pages10
ISBN (Electronic)9781450333337
DOIs
StatePublished - Jan 11 2015
Event6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 - Rehovot, Israel
Duration: Jan 11 2015Jan 13 2015

Publication series

NameITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science

Other

Other6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
CountryIsrael
CityRehovot
Period1/11/151/13/15

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Keywords

  • Leverage scores
  • Matrix sampling
  • Randomized numerical linear algebra
  • Regression

Fingerprint Dive into the research topics of 'Uniform sampling for matrix approximation'. Together they form a unique fingerprint.

  • Cite this

    Cohen, M. B., Lee, Y. T., Musco, C., Musco, C., Peng, R., & Sidford, A. (2015). Uniform sampling for matrix approximation. In ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science (pp. 181-190). (ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science). Association for Computing Machinery, Inc. https://doi.org/10.1145/2688073.2688113