Algorithmic High-Dimensional Geometry I

on YouTube ↗01h 34m

" summary

Shows that random linear maps (Gaussian projections, i.e. the Johnson-Lindenstrauss lemma) cut dimension to k = O(log n / ε^2) and preserves pairwise distances with high probability, then builds locality-sensitive hashes: grid projections give ρ ≈ 1/c while ball‑carving plus low‑dimensional projection achieves ρ = 1/c^2 (query ≈ n^ρ, space ≈ n^{1+ρ}). Gives concrete hash families, K ≈ log n to make far collisions ~1/n, discusses exponential vs polynomial cost to compute buckets and practical time/space tradeoffs.

AI-written summary · about

" chapters (18)

1. 0:00Start
2. 2:24Prism of nearest neighbor search (NNS)
3. 7:102D case
4. 8:10High-dimensional case
5. 9:29Approximate NNS
6. 12:16Heuristic for Exact NNS
7. 13:39Approximation Algorithms for NNS A vast literature: milder dependence on dimension
8. 15:11Motivation If high dimension is an issue, reduce it?! "flatten" dimension d into dimension k «d
9. 17:07Dimension Reduction Johnson Lindenstrauss Lemma: there is a randomized
10. 18:43Idea: Project onto a random subspace of dimension k!
11. 22:34Full Dimension Reduction Just repeat the ID embedding for k times!
12. 23:35Concentration ► F(z) is distributed as
13. 25:15Dimension Reduction: wrap-up
14. 31:17Locality-Sensitive Hashing
15. 38:10NNS for Euclidean space
16. 46:50Putting it all together
17. 47:45Analysis of LSH Scheme
18. 55:00Better LSH ?

" related talks

• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 57mHigh Dimensional Geometry and Concentration ISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 42mk-means and k-medians under Dimension ReductionYury Makarychev · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch IIDavid P. Woodruff · Foundations of Data Science Boot Camp 2018
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018