ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling

We demonstrate that the best k-sparse approximation of a length- $\boldsymbol{n}$ vector can be recovered within a $(1+\boldsymbol{\epsilon})$-factor approximation in $O((k / \epsilon) \log n)$ time using a non-adaptive linear sketch with $O((k / \epsilon) \log n)$ rows and $O(\log n)$ column sparsity. This improves the running of the fastest-known sketch [Nakos, Song; STOC ‘19] by a factor of $\log n$, and is optimal for a wide range of parameters. Our algorithm is simple and likely to be practical, with the analysis built on a new technique we call weighted hypergraph peeling. Our method naturally extends known hypergraph peeling processes (as in the analysis of Invertible Bloom Filters) to a setting where edges and nodes have (possibly correlated) weights.