The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Researchers derive sufficient sample-size conditions for recovering sparse binary signals from sparse Gaussian measurements, quantifying an information-theoretic threshold of order slog(p/s)/log(ds/p).
The paper studies support recovery of sparse binary signals from noisy linear measurements. For sparse Gaussian designs, the authors identify sufficient minimal sample sizes for maximum-likelihood recovery in the high-SNR regime d*s/p -> infinity, yielding an information-theoretic threshold of order slog(p/s)/log(ds/p) that makes the price of measurement sparsity explicit. They also show a regime where the sample-complexity loss from sparsity is only logarithmic while computational gains are nearly linear, and prove that for independently sparsified dense Gaussian designs a sample size of order p/ψ² suffices for support recovery at any fixed error level.
- Sufficient conditions for ML support recovery derived in the high-SNR regime with sparse measurements.
- Measurement sparsity can cost only logarithmic sample complexity while enabling near-linear computational gains.
- For sparsified dense designs, order p/ψ² samples suffice for support recovery in proportional regimes.
Full article175 words · extracted from huggingface.co · click to collapse
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 ψ.
Text extracted automatically; images, tables and formatting may be missing. Original: https://huggingface.co/papers/2509.01809