{"ID":2851077,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.20361","arxiv_id":"2510.20361","title":"$\\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+ε)$-factor approximation in $O((k/ε) \\log n)$ time using a non-adaptive linear sketch with $O((k/ε) \\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.","short_abstract":"We demonstrate that the best $k$-sparse approximation of a length-$n$ vector can be recovered within a $(1+ε)$-factor approximation in $O((k/ε) \\log n)$ time using a non-adaptive linear sketch with $O((k/ε) \\log n)$ rows and $O(\\log n)$ column sparsity. This improves the running time of the fastest-known sketch [Nakos,...","url_abs":"https://arxiv.org/abs/2510.20361","url_pdf":"https://arxiv.org/pdf/2510.20361v1","authors":"[\"Nick Fischer\",\"Vasileios Nakos\"]","published":"2025-10-23T09:01:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}