Sketching High-Dimensional Data

on YouTube ↗01h 10m

" summary

Johnson–Lindenstrauss embedding requires m = O(ε^{-2} log n) and is information-theoretically tight; practical work replaces dense Gaussian maps with faster or sparser constructions. Fast-JL uses a randomized Fourier preconditioner plus sampling to get embedding time ≈ O(d log d) (with a small slow JL wrap-up), while sparse approaches prove the CountSketch with s ≈ εm nonzeros is nearly optimal up to logs. Applications: 1+ε-preserves k‑means cost (you can reduce to m ≈ k/ε^2 or even O(log k) refinements), enable approximate matrix multiplication and sketch‑and‑solve least squares.

AI-written summary · about

" chapters (10)

1. 0:00Introduction to embeddings
2. 3:15Johnson-Lindenstrauss theory
3. 11:25Proofs and distributions
4. 14:18Improving runtime
5. 19:18Sparse constructions
6. 28:52State-of-the-art sparse JL
7. 33:50Applications: K-means
8. 46:44Constrained low-rank
9. 52:59Randomized linear algebra
10. 1:02:50Subspace embeddings

" related talks

• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 48mHomomorphic Sketches: Shrinking Big Data without Sacrificing StructureAndrew McGregor · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 48mInput-sparsity Time Algorithms for Embeddings and Regression ProblemsMichael Mahoney · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 46mSpectral Sparsification of GraphsNikhil Srivastava · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)