Sketching as a Tool for Numerical Linear Algebra
summary
Shows concrete sketching recipes and runtime guarantees: Gaussian JL needs K = Θ(d/ε²) but is dense; a fast JL (Hadamard+sign+sampling) gives O(nd log n) time; count sketch (one nonzero per column) yields a provable subspace embedding with K = Θ(d²/ε²) and multiplies in O(nnz(A)) time, so regression runs in nnz(A)+poly(d,1/ε) time. For L1, a Cauchy sketch gives a D log D distortion, QR preconditioning plus importance sampling produces a 1+ε solution from poly(D)/ε² sampled rows; reciprocal-exponential hashing further reduces samples.
AI-written summary · about
chapters (10)
- 0:00Introduction to sketching
- 0:48Regression basics
- 4:25Closeness measures
- 7:48Sketch and solve
- 10:01Sketching matrices
- 14:26Sparse sketching
- 17:49Proof of correctness
- 31:52L1 regression techniques
- 40:35Sampling and conditioning
- 59:19Conclusion and Q&A
related talks
01h 04mSketching and Randomized Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 10mSketching High-Dimensional Data
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
32mRandomized Numerical Linear Algebra: Overview
31mSimple and Deterministic Matrix Sketches