Foundations and Trends® in Theoretical Computer Science

Volume 10, issue 1–2

Sketching as a Tool for Numerical Linear Algebra

This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the ex...