Sampling for Linear Algebra, Statistics, and Optimization I
summary
Randomized linear‑algebra sketches replace large matrices by sampled rows/columns or random projections (Hadamard, Gaussian, CountSketch) so downstream least‑squares and low‑rank problems run much faster while provably preserving geometry: you get a subspace embedding that serves as a practical preconditioner (set ε≈1/2 for a cheap, robust transform), sample complexity drops to roughly O(d/ε) up to logs vs O(d2) naive, and approximate leverage score sampling finds the few high‑influence SNPs that standard PCA flags; implemented systems have beaten LAPACK on large PCA tasks.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:52Outline Background and Overview
- 2:13RandNLA: Randomized Numerical Linear Algebra
- 9:27Basic RandNLA Principles
- 11:55Element-wise Sampling
- 13:31Row/column Sampling
- 18:51Random Projections as Preconditioners
- 28:24Approximating Matrix Multiplication
- 34:07Subspace Embeddings
- 40:49Two important notions: leverage and condition
- 42:04Meta-algorithm for E-norm regression (2 of 3)
- 48:00Meta-algorithm for Iz-norm regression (3 of 3)
- 48:50Least-squares approximation: the basic structural result
- 52:13Least-squares approximation: RAM implementations
- 55:50Extensions to Low-rank Approximation (Projections)
related talks
32mRandomized Numerical Linear Algebra: Overview
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
48mRandomized Numerical Linear Algebra
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
01h 04mSketching and Randomized Linear Algebra
01h 03mSketching as a Tool for Numerical Linear Algebra
28mRandomized Constrained Matrix Decompositions
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...