Codes and Expansions (CodEx) Seminar

Liza Rebrova (Princeton)
Iterative sketching: from local views to global structure

How can repeated low-dimensional views of a problem exploit its global structure? Random sketching is a broadly used procedure that constructs a useful smaller representation of data. In this talk, I will discuss its role inside iterative sketch-and-project algorithms for solving linear systems, where each sketch provides a local view of the problem and defines a small subproblem whose solution guides the next update. Starting from connections with gradient methods, Kaczmarz, and coordinate descent, I will focus on two choices: the size of each sketch and the information retained across iterations. Spectral analysis explains why larger sketches can benefit from low-rank structure and suggests explicitly identifying and reusing an informative subspace. Finally, we discuss why the resulting algorithms are effective both as linear solvers and as subroutines in broader optimization methods.