Logo

Mathematical Sciences Research Institute

Home » Workshop » Schedules » Random Matrices in Iterative Linear Solvers: Corruption Removal and Sketching

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

September 21, 2021 (11:30 AM PDT - 12:20 PM PDT)
Speaker(s): Liza Rebrova (Princeton University)
Location: MSRI: Simons Auditorium, Online/Virtual
Tags/Keywords
  • Randomized algorithms

  • Block Kaczmarz

  • random matrices

  • concentration of measure

  • Gaussian sketching

  • Noisy linear systems

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification
Video
No Video Uploaded
Abstract

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.

Supplements No Notes/Supplements Uploaded
Video/Audio Files
No Video Files Uploaded