Sketching High-Dimensional Data
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28·
summary
Optimal space for one plus epsilon distinct counting is 1/ε^2 log(1/δ)+log n, and both lower and upper bounds are given; deterministic exact algorithms require linear space so deterministic+exact ⇒ Ω(n), and deterministic 1+ε or randomized exact also fail, so you need both randomness and approximation to get sublinear memory. Practical constructions use linear sketches (a Vandermonde linear sketch for k-sparse recovery that supports deletions) and a support-finder + AGM sketch to build spanning forests in ~n log^3 n space; the sketches are linear and summable, and decoding ranges from exponential to polynomial time.
AI-written summary · about
chapters (10)
- 0:00Review of sketching basics
- 2:36Roadmap and graph sketching
- 3:54Impossibility results
- 6:26Encoding argument proof
- 7:19Inversion and logic details
- 17:51Communication complexity
- 22:46Deterministic approximations
- 35:53Handling deletions
- 37:26Linear sketching techniques
- 47:36Graph sketching and results
related talks
48mHomomorphic Sketches: Shrinking Big Data without Sacrificing Structure
01h 03mSketching as a Tool for Numerical Linear Algebra
35mSampling for Subset Selection and Applications
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 26mStreaming, Sketching and Sufficient Statistics II
55mTheory of Data Streams
31mAnswering Multi-dimensional Queries on Massive Datasets
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke