Randomized Algorithms for Solving Linear Systems with Low-Rank Structure

Iterative methods for solving large systems of linear equations can exhibit extremely slow performance on poorly conditioned matrices. Fortunately, this phenomenon can be addressed for a broad class of problems where the spectrum exhibits low-rank structure, which arise for instance in kernel methods, second-order optimization, or as a result of the underlying properties of the data. A key paradigm which enables tackling low-rank structured problems is randomization, i.e., introducing stochasticity into the algorithmic procedure via techniques such as matrix sketching and sampling. In this talk, I will formalize the task of solving a linear system with low-rank structure, and discuss our recent work on designing and analyzing the complexity of randomized algorithms for preconditioning and solving such systems. In particular, I will show how these methods can outperform state-of-the-art deterministic solvers, such as those based on Krylov subspace methods, both in theory and in practice.