Randomized Linear Algebra - An Introduction

Large scale matrix problems naturally arise in many applications - image processing, text processing, etc. This series of two lectures will provide an overview of the basic ideas relating to solving many of the standard problems - matrix-vector multiply, matrix-matrix multiply, sketch or a low rank approximation of a matrix, approximating the range space of a matrix, etc. using randomized algorithms. First is the data dependent approach based on importance sampling and second is the data independent approach based on random projection. We will discuss two ways of approximating the solution to large scale linear least squares problems.