« search calendars« DIMACS Workshop on Randomized Numerical Linear Algebra, Statistics, and Optimization

« Leverage scores, Christoffel functions, and applications of RandNLA beyond NLA

Leverage scores, Christoffel functions, and applications of RandNLA beyond NLA

September 17, 2019, 10:50 AM - 11:30 AM


Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

Christopher Musco, New York University (NYU)

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.