The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
stat.ML, cs.IT, cs.LG, math.ST
2025-09-02
In high SNR, sparse Gaussian designs need about s log(p/s)/log(ds/p) samples for ML support recovery; after sparsifying a dense design, Θ(p/ψ²) samples suffice.
Sparse recovery asks whether one can find the s non-zero coordinates of β from noisy linear observations Y = Xβ + Z. For dense Gaussian designs the map is already drawn. Below nINF ≈ 2s log(p/s)/log s, recovery is information-theoretically impossible. Above that threshold the maximum-likelihood estimator (MLE) succeeds but is typically exponential-time. Around nALG ≈ 2s log(p−s), Lasso becomes a polynomial-time method that works.
Practitioners often want sparse measurement matrices, with about d non-zeros per row, because they store less and multiply faster. Wang et al. proved necessary sample-size lower bounds; matching sufficient conditions were missing. Chaabouni and Gamarnik (MIT) fill that gap in the high-SNR regime and write the extra samples as an explicit factor. A second question is closer to people who already have dense data: if you sparsify the design after the fact, can you still recover the support?
The signal is restricted to β ∈ {0,1}^p, so recovering the support is recovering the signal. That is a standard reduction in compressed sensing and sparse regression, and it covers signals whose non-zero amplitudes are bounded away from zero by 1.
Sparse measurements: each entry of X is a Bernoulli(d/p) mask times a standard Gaussian, so d is the expected number of non-zeros per row. Observations are Y = Xβ + Z with fixed noise variance σ². SNR is ds/(pσ²). The paper works in high SNR, ds/p → ∞. The estimator is combinatorial MLE: among all s-sparse 0-1 vectors, pick the one with the smallest residual sum of squares.
The proof is a large-deviation bound plus a union bound. A Chernoff estimate controls the chance that a wrong support has smaller MSE than the truth; the technical step is that a measurement row remains Gaussian given its sparsity mask, which pins down the row moment generating function. Union-bounding over supports with Hamming error at least δ yields, for s = o(p),
nSP = 2s log(p/s) / [log(ds/p) + log(δ/(2σ²))].
In the linear-sparsity case s = αp the numerator becomes 2h(α)p, with h the binary entropy.
Active sparsification is a different model. Observations are still generated from a dense Gaussian X, but estimation uses an independently masked X̃ and a response rescaled by d/p. Ỹ is not a noisy projection of β through X̃, so the row MGF depends on the mask, and the natural Chernoff parameter degenerates on an exponentially rare set of masks. They evaluate the bound at a shrunken parameter θ{p,λ} = λθ with λ ∈ (0,1), which removes the degeneracy uniformly. The cost is that ψ must be small enough, and the sample bound carries a (1+ε) slack. The device came out of discussions with Claude Opus 4.7; the authors say every statement was checked by hand.
There are no simulations. The numbers are thresholds. Combined with Wang et al.'s necessary conditions, sparse measurements in high SNR have an information-theoretic phase transition at nINF^SP = 2s log(p/s)/log(ds/p) when s = o(p), or 2h(α)p / log d when s = αp.
| Setting | Information-theoretic threshold | Cost vs dense |
| Dense Gaussian | 2s log(p/s)/log s | 1 |
| Sparse measurements (high SNR) | 2s log(p/s)/log(ds/p) | Γ = log s / log(ds/p) |
| Active sparsification (ψ → 0) | Θ(p/ψ²) | Θ(log p / ψ²) |
Γ can sit just above 1 or diverge, depending on how d and s scale with p. If s = p^α and d = p^β with α+β > 1, then Γ = α/(α+β−1): β near 1 makes sparsity almost free, β near 1−α makes the sample bill explode.
A more operational example: under linear sparsity s = αp, replacing a dense matrix by one with a slowly growing d non-zeros per row lifts the sample size from Θ(p/log p) to Θ(p/log d), at most a logarithmic factor, while matrix-vector cost drops from Θ(p²/log p) to Θ(pd/log d), a nearly linear gain.
On the sparsification side, for every fixed error δ and slack ε, once the keep-rate ψ is small enough, n ≥ (1+ε)nSP makes the fractional Hamming error drop below δ, with nSP = 2h(α)p / log(1 + δψ²/[(1−ψ)(2−δ(1−ψ))]). As ψ → 0 this is Θ(p/ψ²). Inverting the bound, a practitioner who already has n = Ω(p) samples can zero out all but a Θ(√(p/n)) fraction of each row. Doubling n multiplies that sparsification budget by about √2.
Polynomial-time Lasso guarantees for sparse measurements still sit under the Omidiran–Wainwright slow-sparsity assumption (roughly d = ω(p^{2/3}) in the linear-sparsity case). The information-theoretic result here only needs d = ω(1). The algorithmic threshold in between is open.
If you design sketches, compressed-sensing matrices, or sparse features, this paper gives the exchange rate: pay a Γ-fold sample premium, get near-linear storage and multiply savings. If you already collected dense covariates and want to punch holes in the design for cheaper estimation, the budget this proof supports is about √(p/n). Sparser than that sits outside the sufficient condition.
This is a theoretical patch, not a new algorithm. MLE is exponential-time and is not a method you ship. The analogy to network pruning (Optimal Brain Damage and later work) is only an analogy: those results sparsify weights, this one sparsifies the measurement matrix.
The authors are explicit about a gap: the necessity statement rules out exact support recovery uniformly over signals, while sufficiency only gives vanishing fractional Hamming error for the MLE. That is weaker than the dense all-or-nothing theorem. High SNR (ds/p → ∞) is a hard assumption; still-sparser measurements have no sufficient condition here. Active sparsification has no matching necessary bound; they conjecture that sub-proportional keep rates d = o(p) make recovery impossible at any sample size. The small-ψ restriction is a cost of the regularized Chernoff argument, not a claim that larger ψ is intrinsically harder. There are no experiments. Binary signals and combinatorial MLE both limit how far the numbers travel.