Sub-Quadratic Recovery of Correlated Pairs
summary
Claims a sub-quadratic algorithm (n^{2−δ} with small δ) for finding few strong correlated pairs using inner-product-preserving sketches and random grouping, not generic all-pairs comparison. Technique builds a two-layer pipeline: sketch-based bucketing with random ±1 sign flips to reduce collision noise, then decode heavy pair indices via LDPC-style coding and repetition. Prototype recovers planted correlations on a 50×1000 demo and scales if most pairs are near-zero correlated; beating n^2 requires optimistic sparsity and repetitions.
AI-written summary · about
chapters (13)
- 0:00Start
- 1:50"Sketch" Data Structures
- 5:17Looking for Correlations
- 7:14Computing the Correlation
- 11:02Sketching version 1
- 11:21Sketching version 2
- 16:00Bucketing the sketches
- 17:28Coding up the buckets
- 20:47More sketching! Sketch all the things!
- 22:29More coding! Code all the things!
- 25:33Putting it all together
- 27:49Proof-of-concept experiments
- 29:36Outline
related talks
01h 04mSampling Big Ideas in Sublinear Algorithms
01h 09mSketching High-Dimensional Data
01h 13mSketching High-Dimensional Data
01h 26mStreaming, Sketching and Sufficient Statistics II
48mHomomorphic Sketches: Shrinking Big Data without Sacrificing Structure
26mUsing Random Projections to Make Sense of High-Dimensional ...
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching High-Dimensional Data