An Introduction to Randomized Algorithms for Matrix Computations

The emergence of massive data sets, over the past twenty or so years, has led to the development of Randomized Numerical Linear Algebra. Fast and accurate randomized matrix algorithms are being designed for applications like 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).