$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917036335038464 |
|---|---|
| author | Fischer, Nick Nakos, Vasileios |
| author_facet | Fischer, Nick Nakos, Vasileios |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20361 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling Fischer, Nick Nakos, Vasileios Data Structures and Algorithms 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. |
| title | $\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.20361 |