The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

AI summary

Overview

Research area: High-dimensional statistics and statistical learning theory — specifically information-theoretic limits of sparse signal recovery (compressive sensing, sparse linear regression, support recovery), with connections to the neural-network pruning literature.

Technical level: Advanced. The paper is a theory paper built on Chernoff bounds, union bounds over supports, maximum-likelihood estimation theory, and moment generating function asymptotics in high-dimensional scaling regimes.

Scope (one sentence): The paper derives sufficient conditions on the number of samples needed for maximum-likelihood or MSE-based support recovery of a sparse binary signal when the measurement matrix is either sparse Gaussian or a post-hoc random sparsification of an originally dense Gaussian design.

Authors and venue metadata: Youssef Chaabouni and David Gamarnik (Massachusetts Institute of Technology); arXiv:2509.01809v2 [stat.ML], published 2025-09-01 (v2 dated 08 Sep 2026), category stat.ML, license CC BY 4.0.

What This Paper Is About

The paper studies how many noisy linear measurements are needed to identify which coordinates of a sparse binary signal are non-zero. Traditional theory assumes dense measurement matrices with sub-Gaussian entries, but in practice sparse measurement matrices are cheaper to store and faster to multiply. The paper asks two questions: (1) how much extra data does measurement sparsity cost, and (2) if the data matrix is already dense and observed (not designed), can it be randomly sparsified after the fact without destroying the ability to recover the signal?

Key Contributions

1. A sufficient condition and matching information-theoretic threshold for sparse Gaussian measurements. In the high-SNR regime where the signal dimension is p, the signal has s non-zero components, and each measurement row has d expected non-zeros, the paper shows the MLE recovers the support when the sample size exceeds n_INF^SP = 2 s log(p/s) / log(ds/p). Combined with the necessary condition of Wang et al. [22], this yields a phase transition at that threshold.

2. An explicit quantification of the "price of sparsity." The paper defines the inflation factor Γ = log s / log(ds/p) > 1 as the ratio of the sparse-measurement threshold to the dense threshold n_INF = 2s log(p/s)/log s, and identifies a regime where the sample-complexity loss is only logarithmic in p while the computational gain is nearly linear in p.

3. A theory of recovery after active sparsification of a dense design. In the proportional regime s = αp, d = ψp, the paper proves that for every fixed error tolerance δ ∈ (0,1) and every slack ε > 0 there is a ψ_0 = ψ_0(α, δ, ε) > 0 such that a sample size of order p/ψ² suffices for support recovery for arbitrarily small ψ. This yields a "sparsification budget" of ψ ≥ c√(p/n).

4. A methodological device: the shrunken Chernoff parameter. Because the rescaled observations in the sparsification setting are a rescaling of the original observations rather than a noisy projection through the sparsified design, the natural Chernoff parameter introduces a degeneracy on an exponentially small set of masks. The authors resolve this by evaluating the Chernoff bound at θ_{p,λ} = λθ* for λ ∈ (0,1) (Lemma 5.2), which removes the degeneracy uniformly over masks at the cost of a controlled slack. The authors state this device is of independent methodological interest. The paper discloses that this idea emerged from discussions with large language models (Anthropic's Claude Opus 4.7), and that all mathematical statements were fully verified by the authors.

Main Findings

• Phase transition under sparse measurements. In the sublinear sparsity regime s = o(p) with p, s, d → +∞, d = o(p), and ds = ω(p) (equivalently SNR → +∞), recovery is information-theoretically impossible if n ≤ (1-ε) n_INF^SP and guaranteed by the MLE if n ≥ (1+ε) n_INF^SP, where n_INF^SP = 2s log(p/s)/log(ds/p). The impossibility direction is due to Wang et al. [22]; the sufficiency direction is the paper's contribution.

• Two regimes in Theorem 1. For s = o(p), the sufficient threshold is n_SP* = 2s log(p/s) / (log(ds/p) + log(δ/(2σ²))). For s = αp with constant α ∈ (0,1), it is n_SP* = 2h(α)p / (log d + log(δα/(2σ²))), where h(·) is the binary entropy h(x) = -x log x - (1-x) log(1-x). The corresponding Corollary 2 threshold in the second regime is n_INF^SP = 2h(α)p / log d.

• The price of sparsity. Since n_INF^SP ≥ n_INF, sparse measurements always require more samples than dense ones. The exact multiplier is Γ = log s / log(ds/p) > 1. The smaller the density rate d/p, the more expensive the sparsity. In the regime s = p^α, d = p^β with α, β ∈ (0,1) and α + β > 1, Γ = α/(α + β - 1), which approaches 1 as β → 1 (low measurement sparsity) and approaches +∞ as β → 1 - α with α fixed (high measurement sparsity). In the proportional regime s = Θ(p), d = Θ(p), the factor becomes negligible.

• A trade-off between sampling and computation. With φ(x) = x/log x, the paper compares a dense design requiring n_1 = n_INF = Θ(p/log p) samples against a sparse design with d = min(p^{o(1)}, φ^{-1}(o(φ(p)))) expected non-zeros per row requiring n_2 = n_INF^SP = Θ(p/log d) samples. The sample-complexity ratio n_2/n_1 is at most logarithmic in p, while the computational cost of matrix-vector multiplication drops from n_1 p = Θ(p²/log p) to n_2 d = Θ(pd/log d), a computational gain nearly linear in p.

• Broader sparsity than prior algorithms allow. Theorem 1 holds under d = ω(1), whereas the polynomial-time Lasso guarantee of Omidiran and Wainwright [18] requires d/p = ω(s^{-1/3}) and d/p = ω((log log(p-s)/log(p-s))^{1/3}); when s = Θ(p) this demands d = ω(p^{2/3}). The authors note their guarantee tolerates much sparser measurements but comes with potentially super-polynomial computational complexity, since computing the MLE is exponential-time in general. Table 1 of the paper lists the algorithmic sufficient threshold for sparse high-SNR measurements as "Unknown."

• Sparsified-measurement result. For a dense Gaussian design X, the paper forms X̃_{ij} = B_{ij} X_{ij} with B_{ij} ~ Ber(d/p) i.i.d. and uses the rescaled response Ỹ = (d/p) Y. Theorem 3 states that for fixed α, δ ∈ (0,1) and any ε > 0, there exists ψ_0 = ψ_0(α, δ, ε) > 0 such that for ψ ∈ (0, ψ_0) fixed, s = αp, and d = ψp, a sample size larger than n_SP* = 2h(α)p / log(1 + δψ²/((1-ψ)(2 - δ(1-ψ)))) suffices for the MSE minimizer over binary s-sparse vectors to recover the support up to error fraction δ, meaning |Supp(β*) Δ Supp(β̂)| < 2δs.

• The price of sparsification scales as p/ψ². In the strong-sparsification regime where ψ → 0, the sufficient threshold is n_INF^SP = Θ(p/ψ²). The authors attribute this cost not to measurement sparsity but to a bias in the observations.

• A sparsification budget. Inverting the bound in the regime n = Ω(p), recovery after active sparsification holds as long as ψ ≥ c√(p/n) for some constant c > 0. Practical reading: with n observations a practitioner may zero out all but an order-√(p/n) fraction of the design's entries per row and still recover the signal; doubling the sample size buys an additional factor of √2 in sparsification budget.

• Stated limitation. Remark 2.1 notes that the necessity statement (from [22]) negates exact support recovery uniformly over signals, while the sufficiency statement establishes only vanishing fractional Hamming error in probability. The two are logically compatible, so Corollary 2 establishes a phase transition weaker than the All-or-Nothing phenomenon of Reeves, Xu and Zadik [19] established in the dense setting.

• The smallness of ψ is a proof artifact. The authors state explicitly that the condition on ψ is the cost of the Chernoff-parameter regularization, not a claim that larger ψ is intrinsically harder.

Methodology in Plain English

The paper is theoretical; the provided content reports no numerical experiments or simulations. The argumentative structure is as follows.

The signal is assumed binary (β* ∈ {0,1}^p) with exactly s non-zeros, so recovering the support is equivalent to recovering the signal. The estimator studied is the maximum-likelihood estimator, which minimizes the squared error ||Y - Xβ||² over all binary s-sparse β. The measurement matrix is a "sparse Gaussian" matrix, formed as the elementwise product of a Bernoulli mask with probability d/p and independent standard Gaussian entries.

To show that the estimator succeeds, the authors compare the loss of the true support against the loss of any competing support whose symmetric difference with the truth is at least 2δs. For each such competitor, the event that it beats the truth is rare, and a Chernoff bound controls its probability, with the bound taking the form (n/2)(log(2σ²p/(δds)) + o(1)). A union bound over the binom(p,s) possible supports then gives a failure probability bounded by binom(p,s)(2σ²p/(δds))^{n/2}. Solving for n yields the threshold. The sharpness of the threshold comes from a tight asymptotic analysis of the row moment generating function, which exploits the fact that a measurement row is conditionally Gaussian given the random pattern of which of its entries are non-zero.

The sparsification problem requires a different treatment because the observations are a rescaled version of the original dense observations, not a clean noisy projection through the sparsified design. As a result, the relevant row moment generating function depends on the realization of the random sparsification mask, and the most natural Chernoff parameter becomes degenerate on an exponentially small set of masks. Treating that directly would require an unverified uniform-integrability hypothesis. The authors instead evaluate the Chernoff bound at a shrunk parameter, which removes the degeneracy uniformly over masks and costs a controlled slack that the (1+ε) slack in the sample-size assumption absorbs.

Why This Matters

Impact on research. Prior work by Wang et al. [22] established only necessary conditions for recovery under sparse measurements, leaving open the question of how many samples are actually enough. This paper supplies the matching sufficiency side for the high-SNR regime, closing the gap into a phase transition at an explicit threshold, and quantifies the penalty as a formula rather than a qualitative statement. It also extends the analysis of "missing covariates" / missing-at-random designs (studied by Loh and Wainwright [15] for dense Gaussian designs and constant missingness rate) to information-theoretic support-recovery thresholds in a strong sparsification regime. The paper connects its sparsification question to the neural-network compression lineage of Optimal Brain Damage (LeCun, Denker and Solla [14]) and Optimal Brain Surgeon (Hassibi and Stork [11]), noting that the object being sparsified differs (estimator parameters there, measurement matrix here) but the post-hoc sparsification question is shared.

Real-world applications (as listed by the paper, spanning both "designed X" and "observed X" settings):

• Compressive sensing hardware, including single-pixel cameras, MRI scanners, and radar remote-sensing systems, where measurement matrices can be designed and therefore directly sparsified to reduce storage and computation.
• Error-correction schemes in digital communications and widely used image-compression formats, where the signal model is sparse and reconstruction is the downstream task.
• Signal denoising and sparse regression, where the measurement matrix is observed rather than designed — the setting that motivates the paper's active-sparsification analysis.
• Data stream computing and combinatorial group testing, both cited among the motivating applications of sparse recovery.

Industry relevance. The paper gives practitioners an exact design rule: for designed measurement matrices, it specifies how sparse a matrix can be made and how the resulting sample requirement scales, with the observation that in the nearly dense proportional regime the sample penalty vanishes. For observed dense data, it provides an explicit sparsification budget ψ ≥ c√(p/n), telling a practitioner how much of a design can be zeroed out given a fixed dataset size — directly relevant to memory and compute costs in large-scale regression and compressed-data pipelines. The paper cautions that these guarantees are information-theoretic, not algorithmic: the MLE is exponential-time in general, and the paper does not resolve whether polynomial-time algorithms can match it in the sparser regimes.

Future Directions

• Strengthen to All-or-Nothing. Remark 2.1 states the authors believe an analogous All-or-Nothing strengthening of Corollary 2 should hold in the sparse-measurement setting, and leave it to future work.
• Find the algorithmic threshold under sparse measurements. Table 1 lists the algorithmic sufficient threshold for sparse high-SNR measurements as "Unknown." The paper notes its sufficiency result covers a strictly broader sparsity regime than the condition in (2), leaving open the possibility of corresponding polynomial-time improvements in that regime.
• Remove or relax the smallness condition on ψ. The authors state that the condition ψ < ψ_0(α, δ, ε) is the cost of the shrunken-Chernoff-parameter regularization, not evidence that larger ψ is intrinsically harder, implying the regularization could be improved.
• Determine the exact value of ψ_0. The theorem asserts existence of ψ_0(α, δ, ε) > 0 but the provided content does not report an explicit expression, leaving the quantitative boundary of the guarantee unresolved.

Target Audience

Theoretical researchers in high-dimensional statistics, statistical learning theory, and information theory who work on sparse recovery, support recovery thresholds, and compressive sensing; researchers interested in the missing-covariates / missing-at-random regression literature; and theoretically inclined practitioners in medical imaging, remote sensing, communications, and large-scale sparse regression who need to decide how sparse a measurement design can be made. The paper is also of interest to readers tracking how large language models are used as technical discussion partners in mathematical research, since the authors disclose this use explicitly. It is not an introductory read; familiarity with Chernoff bounds, union bounds over combinatorial sets, and high-dimensional asymptotics is assumed.

Authors’ 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 $s\log(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 $ψ$.