The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik · 2025
Read The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements by Youssef Chaabouni, David Gamarnik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01809.txt.
Description
Youssef Chaabouni and David Gamarnik study when a sparse signal can be recovered from few noisy measures. A sparse signal has only a few nonzero parts among many slots. Their measures use sparse random matrices, where each row touches few slots. They find conditions on how many measures suffice for best likelihood recovery when noise is low.
Paired with known lower bounds, their result gives a sharp threshold for the needed sample count. One regime stands out: sparsity costs only a modest factor in samples but gains nearly proportional savings in computation. They also study thinning a dense design after data are taken. Even heavy thinning still allows recovery with a stated sample size in their proof.
Catalog record
| CREATOR | Youssef Chaabouni, David Gamarnik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-01809