Sketching as a Tool for Numerical Linear Algebra

By David P. Woodruff. 2014

1,373 citations recorded by the source corpus.

This survey highlights the recent advances in algorithms for numericallinear algebra that have come from the technique of linear sketching,whereby given a matrix, one first compresses it to a much smaller matrixby multiplying it by a (usually) random matrix with certain properties.Much of the expensive computation can then be performed onthe smaller matrix, thereby accelerating the solution for the originalproblem. In this survey we consider least squares as well as robust regressionproblems, low rank approximation, and graph sparsification.We also discuss a number of variants of these problems. Finally, wediscuss the limitations of sketching methods.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Peter Richtárik
  2. Nicolas Loizou
  3. Jakub Konecný
  4. Martin Jaggi
  5. Simon Lacoste-Julien
  6. Francis R. Bach
  7. Sebastian U. Stich
  8. H. Brendan McMahan

In Computational Theory and Mathematics

  1. Nicolas Loizou
  2. David P. Woodruff
  3. Jakub Konecný
  4. Peter Richtárik
  5. H. Brendan McMahan
  6. Francis R. Bach
  7. Shusen Wang
  8. Peilin Zhong

In Optimization & Training

  1. Peter Richtárik
  2. Nicolas Loizou
  3. Jakub Konecný
  4. Simon Lacoste-Julien
  5. Martin Jaggi
  6. Francis R. Bach
  7. H. Brendan McMahan
  8. Sebastian U. Stich

In Numerical Methods & Scientific Computing

  1. Nicolas Loizou
  2. Jakub Konecný
  3. Joel A. Tropp
  4. Francis R. Bach
  5. Cameron Musco
  6. Christopher Musco
  7. Dmitry Babichev
  8. Chandrashekar Lakshminarayanan

Citations in the corpus