I will give an overview of the recent line of work on learning-based algorithms for the low-rank approximation problem. Such algorithms use training sets of input matrices in order to optimize their performance. Specifically, some of the most efficient approximate algorithms for computing low-rank approximations to a matrix A follow the following two step process: first compute a “sketch” SA, where S is a random m×n "sketching matrix", and then perform the singular value decomposition of SA. Their learning-based versions replace the random matrix S with a "learned" matrix, which results in significant reduction of the approximation error.

Joint work with Peter Bartlett, Yang Yuan, Ali Vakilian, Tal Wagner, David Woodruff