Statistics Seminar
Two faces of sketching: from iterative linear solvers to randomized singular value decomposition by Elizaveta Rebrova
Event Details
Date: October 19, 2022
Speaker: Elizaveta Rebrova
Website: https://erebrova.github.io/
Title: Two faces of sketching: from iterative linear solvers to randomized singular value decomposition
Abstract: The sketch-and-project is a unifying framework for many known projective iterative methods for solving linear systems Ax = b, as well as their extensions to non-linear optimization problems. I will talk about our recent work with D. Needell and M. Derezinski that gives lower bounds for the convergence rate of the sketch-and-project methods via new tight estimates for the spectrum of the expected sketched projection matrix. Our estimates reveal a connection of this rate with the other well-known but seemingly unrelated quantity related to randomized sketching, namely, the Randomized SVD error of the matrix. This new approach gives a way (a to capture the influence of the sketch size on the convergence, depending on the spectral properties of the matrix A, and (b) to give the convergence guarantees for very sparse sketch matrices, thus bringing us closer to quantifying the efficiency of the block sketching (that notoriously outperforms previously available convergence guarantees).