Randomized Numerical Linear Algebra: Overview
summary
Survey of methods that turn giant matrices into small matrix sketches by sampling columns, rows or entries or by random projections and then run standard algorithms on the sketch. Gives concrete guarantees: Frobenius and spectral-norm error bounds via matrix Bernstein/Chernoff, sample sizes like O(d/epsilon + d log d) for overconstrained least squares, and relative-error low-rank SVD via Krylov/subspace iteration with Q ~ log(rank/epsilon)/sqrt(gap). Covers leverage-score sampling, input-sparsity‑time projections, elementwise sampling and connections to matrix completion.
AI-written summary · about
chapters (18)
- 0:00Intro
- 2:10Why RandNLA?
- 6:04RandNLA in a slide
- 8:55Interplay
- 10:44RandNLA: Column/row sampling
- 11:37Approximating AAT by CCT
- 12:47The algorithm (matrix notation, cont'd)
- 14:11Error bounds: Frobenius norm
- 15:50Error bounds: spectral norm
- 19:50Least-squares problems
- 20:35Algorithm: Sampling for La regression
- 22:02Leverage scores: tall & thin matrices
- 23:02Computing leverage scores
- 27:29RandNLA for SVD: early approaches
- 28:00RandNLA for SVD: subspace iteration
- 28:26RandNLA for SVD: Krylov subspace
- 29:58Element-wise sampling: overview
- 30:43Element-wise leverage scores
related talks
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
48mRandomized Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
01h 04mSketching and Randomized Linear Algebra
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods