Random Matrices in Iterative Linear Solvers: Corruption Removal and Sketching
[HYBRID WORKSHOP] Connections and Introductory Workshop: Universality and Integrability in Random Matrix Theory and Interacting Particle Systems, Part 2 September 20, 2021 - September 24, 2021
Location: MSRI: Simons Auditorium, Online/Virtual
concentration of measure
Noisy linear systems
When it is infeasible to solve a large linear system directly by inversion, light and scalable randomized iterative methods can be used instead, such as, Randomized Kaczmarz (RK) algorithm, or Stochastic Gradient Descent (SGD). I will discuss some cases when the questions from the non-asymptotic random matrix theory are inherent for proving convergence guarantees for these methods. This includes QuantileRK and QuantileSGD methods proposed for the systems that might contain large, sparse, potentially adversarial corruptions. Unlike the classical extensions of RK/SGD to noisy (inconsistent) systems, the new methods learn to avoid corruptions rather than tolerate the small noise, and result in exact convergence when up to one half of the equations can be arbitrarily corrupted. The second case is connected to the sketching techniques that considerably speed up the iterative solvers. Based on the joint work with Deanna Needell, Jamie Haddock and Will Swartworth.