The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
Massachusetts Institute of Technology
Published September 8, 2026 · on the feed September 10, 2026 · ▲ 4 · arXiv 2509.01809
The 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 ψ.
The Brief
2:18A short podcast summary of the paper. Written and voiced by AI.
Transcript
The Price of Sparsity. Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements. By Youssef Chaabouni and one other, from the Massachusetts Institute of Technology. Published on the eighth of September. No code repository is linked to it.
The problem is support recovery. A signal is sparse and binary: most of its entries are zero, and the task is to find which ones are not, from noisy linear measurements. The letter p is the signal's dimension, s is how many components are non-zero, and d is the expected number of non-zero entries in each row of the measurement matrix. A small d means sparse measurements. The question is what that sparsity costs in samples.
The first result concerns sparse Gaussian measurement matrices, recovered by maximum likelihood in the high-SNR regime, where d times s over p grows without bound. The paper identifies sufficient conditions on the minimal sample size there. Combined with known lower bounds, this gives an information-theoretic threshold of order s times the log of p over s, divided by the log of d s over p. That denominator makes the price of measurement sparsity explicit.
The second result starts from an ordinary dense Gaussian design. The observations come from it, but estimation uses an independently sparsified copy together with a rescaled response. In the proportional regime, s equal to alpha times p and d equal to psi times p, the authors prove that for every fixed target error level delta and every positive slack epsilon, a sample size of order p over psi squared suffices for support recovery, however small psi is made.
For the first result, the new sufficient condition is paired with lower bounds that already exist, and together they pin down the threshold. Reading the formula, the whole cost of sparse measurement sits in the log of d s over p. The authors highlight a regime where the loss in sample complexity from measurement sparsity is only logarithmic, while the computational gain is nearly linear.
The conditions are specific. Signals are binary. The first assumes maximum-likelihood recovery with sparse Gaussian matrices, in the high-SNR regime. The second holds in the proportional regime, with the sparsified design drawn independently of the dense one that produced the data.
Sparsity, then, is not free, but its price can be written down as a formula, and in the right regime it is a logarithm paid for a nearly linear saving.
Paper Quest · 7 chapters · about 35 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
Every quest starts with a wall. Here it is a simple question: what does a cheap, sparse measurement really cost?
You want to find which entries of a long binary signal are non-zero, from noisy linear measurements. Each measurement row is a random Gaussian combination of the signal's entries.
The road ahead
- 1 · The problem ~6 min Sparse measurement rows are cheap to use, but nobody knew how many extra measurements they cost when rows get very sparse.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min The paper proves how many samples suffice for maximum-likelihood recovery with sparse Gaussian rows, which with known lower bounds pins down the threshold.
- 4 · Choose your own research ~3 min
- 5 · How it works ~3 min
- 6 · The experiment ~6 min You’ll guess: In the regime the authors highlight, how large is the sample-complexity loss caused by using sparse measurements?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.