Mathematics Seminar - Maike Meier MSc, University of Oxford

Title: Randomized algorithms for least squares problems: how to ensure speed and accuracy?

Abstract:

Least squares (LS) problems are ubiquitous in science and engineering, yet the size of modern LS problems is steadily moving beyond the reach of classical algorithms. Randomized algorithms have been shown to be incredibly effective at computing fast solutions to large-scale highly overdetermined LS problems. Such algorithms are based on randomized dimension reduction, also known as sketching, to compute a preconditioner for the LS problem. In this talk, the sketch-and-precondition framework is introduced, and then shown to be numerically unstable. We discuss existing approaches to stabilizing the algorithm, which are never fully satisfactory in terms of speed or stability. We then introduce the SPIR algorithm, which solves the open problem of the existence of a randomized LS solver that is both fast and stable. SPIR combines the sketch-and-precondition framework with iterative refinement to obtain a backward stable LS solver with better computational complexity than classical solvers. This algorithm offers the promise of incorporating randomized LS solvers into existing software libraries while maintaining the same level of accuracy as classical solvers.