Abstract: 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, developments in high-dimensional probability (matrix concentration inequalities, matrix coherence), numerical issues (problem conditioning), and the analysis of the error due to randomization. This talk draws on work with current and former students Jocelyn Chi, John Holodnak, Arnel Smith, and Thomas Wentworth.

Bio: Ilse Ipsen received a Bachelor’s degree from the University of Kaiserslautern in Germany and a Ph.D. from Penn State, both in Computer Science. She taught Computer Science at Yale for 10 years, and is now a Distinguished Professor of Mathematics at NC State, with an affiliate appointment in Statistics.