Randomized Numerical Linear Algebra - Overview

Explore the field of Randomized Numerical Linear Algebra (RandNLA) in this 32-minute lecture by Petros Drineas from Purdue University. Delve into the fundamentals of RandNLA, understanding its importance and applications in modern computational mathematics. Learn about column and row sampling techniques, approximation methods for matrix products, and error bounds in Frobenius and spectral norms. Discover algorithms for solving least-squares problems and computing leverage scores for tall and thin matrices. Examine various approaches to Singular Value Decomposition (SVD) in RandNLA, including early methods, subspace iteration, and Krylov subspace techniques. Conclude with an overview of element-wise sampling and its leverage scores, gaining a comprehensive understanding of this powerful tool in numerical linear algebra.

Intro
Why RandNLA?
RandNLA in a slide
Interplay
RandNLA: Column/row sampling
Approximating AAT by CCT
The algorithm (matrix notation, cont'd)
Error bounds: Frobenius norm
Error bounds: spectral norm
Least-squares problems
Algorithm: Sampling for La regression
Leverage scores: tall & thin matrices
Computing leverage scores
RandNLA for SVD: early approaches
RandNLA for SVD: subspace iteration
RandNLA for SVD: Krylov subspace
Element-wise sampling: overview
Element-wise leverage scores