Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II

on YouTube ↗01h 10m

" summary

Shows that CountSketch JL moment (L=2) gives an unbiased subspace embedding with variance O(1/K) and needs about K = 2/(ε^2 δ) rows to get the desired moment bound (and explains the D^2 collision lower bound on hashing). Uses S·A and a QR to produce an R that makes the condition number → O(1) so gradient descent needs O(log(1/ε)) iterations, each doing matrix–vector products in NNZ(A) time, yielding run time NNZ(A)·log(1/ε) for high‑precision regression. For low‑rank, sketch to ~k/ε rows, project rows into that row‑span and SVD the smaller matrix in NNZ(A)+n·poly(k/ε) time.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 5:47CountSketch Satisfies the JL Property
3. 12:42Outline
4. 12:54High Precision Regression
5. 13:48Small QR Decomposition
6. 32:17Finding a Constant Factor Solution
7. 45:31What is a good low rank approximation?
8. 48:24Solution to low-rank approximation [S]
9. 51:53What is the matrix S?
10. 52:32Caveat: Projecting the points onto SA is Slow
11. 55:54Why do these Matrices Work?

" related talks

• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 31mSimple and Deterministic Matrix SketchesEdo Liberty · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)