Streaming, Sketching and Sufficient Statistics II
summary
Covers L0 sampling and L2 sampling with concrete constructions: geometric-level subsampling plus sparse recovery produces an L0 sampler that lets sketches of nodes be summed so internal edges cancel, enabling streamed connected-component recovery; random reweighting by u_i gives L2 samples and an unbiased estimator for F_k that requires about N^{1-2/k}/epsilon^2 repetitions; row/column sketches approximate AB with Frobenius error O(epsilon ||A||_F ||B||_F); Index/Disjointness reductions yield matching lower bounds (e.g. F0 and F_infty hardness).
AI-written summary · about
chapters (11)
- 0:00Introduction to sketching
- 0:48Advanced sketching topics
- 2:32Uniform sampling concepts
- 7:50L-p sampling distributions
- 11:32L0 sampling constructions
- 20:00Sparse recovery algorithms
- 27:22Graph connectivity algorithms
- 40:02L2 sampling for moments
- 53:23Matrix multiplication
- 1:00:01Lower bounds and complexity
- 1:16:23Future research directions
related talks
01h 06mData Streams I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 21mAn Overview on Data Streams Algorithms
55mTheory of Data Streams
35mSampling for Subset Selection and Applications
01h 04mSketching and Randomized Linear Algebra
01h 13mSketching High-Dimensional Data
01h 02mSampling for Linear Algebra, Statistics, and Optimization II