| title | The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements |
|---|---|
| authors | Youssef Chaabouni, David Gamarnik |
| date | 2026-09-08 |
| venue | arXiv (preprint, not peer reviewed) |
| id | arXiv:2509.01809 |
| affiliation | Massachusetts Institute of Technology |
| upvotes | 2 (Hugging Face Daily Papers, 2026-11-01) |
| links | abs pdf hf |
| abstract | We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p to infty, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog(p/s) / log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=αp, d=ψp, we prove that, for every fixed target error level δ and every slack varepsilon>0, a sample size of order p/ψ^2 is sufficient for support recovery for arbitrarily small ψ. |
cite
@misc{chaabouni2026price,
title={The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements},
author={Youssef Chaabouni and David Gamarnik},
year={2026},
eprint={2509.01809},
archivePrefix={arXiv},
url={https://arxiv.org/abs/2509.01809}
}