Module III: Randomized Algorithms for Linear Algebra (RALA)

This module addresses the challenge of solving large-scale linear algebra problems in the big data era, where classical methods become computationally infeasible. The approach uses randomization to achieve good approximate solutions in shorter time while guaranteeing quality. The problem is solved in two stages: first, randomization is used to obtain a 'sketch' of the matrix and/or develop a basis for the range space; then classical algorithms provide provably good approximate solutions. Topics include sampling-based approaches for matrix-vector and matrix-matrix products, matrix sketching, SVD, CUR decomposition, and fast randomized methods for solving large-scale overdetermined linear least squares problems using both sampling and random projection approaches.