Dimensionality Reduction Via Sparse Matrices

on YouTube ↗42m

" summary

Shows sparse Johnson–Lindenstrauss matrices that embed N points to m = O(ε^{-2} log N) rows while reducing per-column nonzeros s by an Θ(ε) factor versus prior sparse constructions, gives near‑optimal lower bounds (any linear oblivious map needs similar sparsity up to log factors), and offers two concrete constructions: hashing without replacement and a CountSketch blocks variant. Analysis uses a moment-method with graph encoding plus Tutte–Nash‑Williams to bound traces; sparse Pi yields embedding time O(s · nnz(x)) and practical subspace‑embedding tradeoffs (polylog losses in m or s).

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 1:02Metric Johnson-Lindenstrauss lemma
3. 1:44How to prove the JL lemma
4. 2:40Proving the distributional JL lemma
5. 3:13Fast JL Transforms
6. 4:16Where Do Sparse Vectors Show Up?
7. 4:59Sparse JL transforms One way to embed sparse vectors faster: use sparse matrices
8. 8:41Sparse JL Constructions in matrix form
9. 10:52Natural "matrix extension" of sparse JL
10. 13:12Remarks
11. 14:45Motivation for matrix extension of sparse JL
12. 15:32Numerical linear algebra
13. 16:16Computationally efficient solutions
14. 17:56How to use subspace embeddings
15. 19:49Analysis (L=2)
16. 22:15Analysis (large )
17. 23:15Example monomial-graph correspondence
18. 30:27Understanding G
19. 31:06Bounding F(G) with odd multiplicities
20. 33:29AM-GM trick done right
21. 36:03Other recent progress
22. 38:43Open Problems

" related talks

• 01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch IIDavid P. Woodruff · Foundations of Data Science Boot Camp 2018
• 01h 34mAlgorithmic High-Dimensional Geometry IAlex Andoni · Big Data Boot Camp 2013
• 59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch IDavid P. Woodruff · Foundations of Data Science Boot Camp 2018
• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 05mWhy You Should Care about Sparse MatricesJeff Trull · C++Now 2019
• 44mConcentration Inequalites in Learning with KernelsDevdatt Dubhashi · Functional Inequalities in Discrete Spaces with Applications 2013
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018