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

on YouTube ↗59m

" summary

Shows that CountSketch matrices (hash rows, random ±1 signs) give a subspace embedding for regression with one non-zero per column and k = Θ(d^2/ε^2) rows, so SA is computable in O(nnz(A)) time and regression reduces to solving a k×d system in poly(d/ε) time. Proof uses an approximate matrix product bound derived from a JL-moment condition (unbiased sketch, variance and higher moments control) and yields only linear dependence on failure probability δ.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:35Outline
3. 1:06Regression analysis
4. 8:57Moore-Penrose Pseudoinverse
5. 10:13Time Complexity
6. 10:38Sketching to solve least squares regression
7. 21:05How to choose the right sketching matrix S? [S]
8. 24:28Faster Subspace Embeddings S CW,MM,NN
9. 27:15Simple Proof ANW
10. 35:45Matrix Product Result [Kane, Nelson]
11. 39:25From Vectors to Matrices
12. 54:43CountSketch Satisfies the JL Property

" 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)
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 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
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)