The emergence of massive data sets, over the past twenty or so years, has lead to the development of Randomized Numerical Linear Algebra. Fast and accurate randomized matrix algorithms are being designed for applications in machine learning, population genomics, astronomy, nuclear engineering, and optimal experimental design.
We give a flavour of randomized algorithms for the solution of least squares/regression problems. Along the way we illustrate important concepts from numerical analysis (conditioning and pre-conditioning), probability (concentration inequalities), and statistics (sampling and leverage scores).
This is a joint ACA–CCIMI seminar