Christopher Musco, New York University (NYU)

Abstract

Leverage scores have arisen as a central and powerful tool in randomized numerical linear algebra. These scores measure the "importance" of rows or columns in a matrix and can be used to design fast randomized algorithms for regression, low-rank approximation, kernel learning, and many other matrix problems. In this talk, I will illustrate the potential of leverage scores to bring the power of randomization to an even broader class of problems in computational mathematics and signal processing. In particular, I will introduce a simple generalization of leverage scores to continuous linear operators and survey applications to polynomial curve fitting, bandlimited function interpolation, off-grid sparse Fourier transforms, and signal covariance estimation. Such applications present an exciting opportunity to apply ideas from RandNLA to new domains. I will devote a large portion of the talk to illustrating connections between randomized methods and classical tools in approximation theory. I will also discuss several open questions.

Video