Random Matrices in Iterative Linear Solvers: Corruption Removal and Sketching

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.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.