Algorithmic High-Dimensional Geometry II
summary
Shows that datasets with doubling dimension λ admit ANN by projecting to O(λ) dimensions with asymmetric contraction/expansion guarantees and by using navigating-nets/cover-trees with linear space and query time exponential in λ. Builds a randomly shifted quadtree embedding that maps sets in a Δ×Δ grid to L1 by counting points per cell and proves EMD→L1 with O(log Δ) distortion in expectation (probability a pair is cut ≈ dist/K so K cancels across scales). Surveys sketching, iterative product norms for Ulam/edit variants, and communication-complexity links; notes EMD embedding is practical, other algorithms may have large constants.
AI-written summary · about
chapters (8)
- 0:00Introduction to high dimensions
- 1:04Small effective dimensions
- 14:01Metric embeddings overview
- 24:05Earth Mover Distance embedding
- 34:45Decomposition and analysis
- 53:12Advanced metric embeddings
- 1:07:44Iterated product spaces
- 1:14:18Sketching and concluding remarks
related talks
01h 01mNearest Neighbor Methods II
01h 04mRandomized Embeddings and Neural Networks
57mHigh Dimensional Geometry and Concentration I
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
11mGeometric Methods for Machine Learning and Optimization
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 12mRecent Progress in High-Dimensional Learning
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces