We present a 'user-friendly' introduction to randomized matrix algorithms, with several case studies that focus on the ideas and intuition behind randomization.
The concerted development of randomized matrix algorithms started in the theoretical Computer Science community in the nineteen-nineties. At first a purely theoretical enterprise, these algorithms have become practical to the point that they are being used by domain scientists; and general purpose software libraries, such as RandBLAS and RandLAPACK, are under development.
Many randomized matrix algorithms reduce the problem dimension by replacing the original matrix with a lower-dimensional 'sketch'. We illustrate this on the basic problem of matrix multiplication, and on the solution of least squares/regression problems. Along the way, we discuss sampling modalities (data-aware, oblivious), developments in high-dimensional probability (matrix concentration inequalities, matrix coherence), numerical issues (problem conditioning), and the analysis of the error due to randomization.