Sketching High-Dimensional Data
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28·
summary
Linear sketches estimate norms and heavy hitters with concrete bounds: AMS sketch uses m = Θ(ε^{-2}) rows and O(ε^{-2} log(1/δ)) words to get 1+ε L2 estimates, and the sparse CountSketch gives constant update time with the same space and uses O(log n) repetitions for high success probability. p‑stable sketches handle 0<p≤2 by taking medians of πx entries with m = Θ(ε^{-2}); bounded independence (k = Θ(ε^{-p})) suffices. For p>2 there is a lower bound Ω(n^{1−2/p}) bits. CountSketch also recovers k,2‑frequent items in O(k log n) space.
AI-written summary · about
chapters (14)
- 0:00Start
- 13:15Gaussian Distribution
- 13:31Central Limit Theorem
- 14:53What Is Index Algorithm
- 29:08Entries within a Row
- 36:03Public Randomness
- 36:27One-Way Communication
- 38:53Hard Case
- 39:23Randomized Protocol
- 48:04Dimensionality Reduction
- 58:02Count Sketch Matrix
- 58:38The Count Sketch Matrix
- 1:08:19The L1 L2 Norm
- 1:11:56Is There a Sparse Version for Faster Update Time for Lp Norm Estimation
related talks
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 03mSketching as a Tool for Numerical Linear Algebra
48mHomomorphic Sketches: Shrinking Big Data without Sacrificing Structure
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
01h 26mStreaming, Sketching and Sufficient Statistics II
55mTheory of Data Streams
31mAnswering Multi-dimensional Queries on Massive Datasets
35mSampling for Subset Selection and Applications