${\ell }_2/{\ell }_2$ Sparse Recovery via Weighted Hypergraph Peeling

Abstract

We demonstrate that the best $k$-sparse approximation of a length-$n$ vector can be recovered within a $(1+\hat{I}\mu )$-factor approximation in $O((k/\hat{I}\mu )\log n)$ time using a non-adaptive linear sketch with $O((k/\hat{I}\mu )\log n)$ rows and $O(\log n)$ column sparsity. This improves the running time 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.

Appears at FOCS '25