Sketching and Randomized Linear Algebra
summary
Shows that random sketches preserve norms and dot products via the Johnson-Lindenstrauss lemma (r = Θ(1/ε^2 log 1/δ)), extend to approximate matrix product with Frobenius error O(ε)||A||_F||B||_F, and give subspace embeddings that need about d/ε^2 rows (SRHT) versus d^2/ε^2 for a naive Gaussian argument. Describes fast sketches: subsampled randomized Hadamard transform yields SA in O(nd log n) time, CountSketch gives SA in O(nnz(A)) time, and sketched preconditioning plus O(log 1/ε) gradient steps produces a 1+ε regression solution.
AI-written summary · about
chapters (6)
- 0:00Introduction to sketching
- 10:22Subspace embeddings
- 20:23Application to regression
- 25:59Efficient sketching methods
- 35:02Preconditioned gradient descent
- 55:11Advanced topics and wrap-up
related talks
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
32mRandomized Numerical Linear Algebra: Overview
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
31mSimple and Deterministic Matrix Sketches