Past, Present and Future of Randomized Numerical Linear Algebra II
summary
Claims concrete speed and accuracy tradeoffs for randomized matrix methods and shows what actually gets built and tested: use statistical leverage scores to sample informative rows or columns, or apply structured random projections to uniformize them, yielding provable relative‑error bounds and rank preservation with far fewer columns than naive sampling. Algorithms run in about ND log D time or in sparse input time, give ~20–50% wall‑time gains on tall dense least squares and empirically beats LAPACK on many tall cases, scale to ~60k×5k, and produce parallel versions (notably LSRN) and a terabyte L1 MapReduce implementation that works in practice.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:55Algorithms for largescale data
- 3:45Sketching matrices
- 8:22Why randomized algorithms
- 12:06Better worst case theory
- 12:28Why do they work
- 17:37Orthogonal matrices
- 19:37The gap between theory and practice
- 21:05Applications in astronomy
- 26:44Vanilla algorithm
- 36:35Smart sampling
- 42:48Preserving rank
- 44:32Fast random projection
- 56:13Low rank approximation
related talks
32mRandomized Numerical Linear Algebra: Overview
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
48mRandomized Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
28mRandomized Constrained Matrix Decompositions
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
35mRandomized Algorithms for Computing Full Matrix Factorizations