Source-linked AI summary
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
TL;DR
The paper asks how sparse measurements affect the sample size needed for support recovery and studies both intrinsically sparse designs and sparsified dense designs. It derives sufficient recovery conditions, identifies the price of measurement sparsity, and shows that strong active sparsification remains viable with sufficiently many samples.
Problem
The paper studies how many noisy linear measurements are needed to recover the support of sparse binary signals when measurements are sparse or obtained by sparsifying a dense design.
Method
The paper analyzes maximum-likelihood or MSE-based support recovery using Chernoff bounds and union bounds for sparse Gaussian designs and independently sparsified dense designs.
Results
The paper establishes an information-theoretic threshold with price of sparsity Γ = log s/log(ds/p), and proves recovery for s = αp, d = ψp with sufficiently small fixed ψ and sufficiently large sample size.
Takeaways & Limitations
Measurement sparsity creates an explicit sampling–computation trade-off, while active sparsification of dense data can still permit support recovery in the strong-sparsification regime.
Takeaways & Limitations
The sparse-measurement necessity and sufficiency statements concern different recovery notions, and the active-sparsification theorem does not hold below n = Ω(p).
Abstract
from arXiv · showhide
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 $ψ$.
1. Introduction.
The paper studies how measurement sparsity affects support recovery of sparse binary signals, establishing sample-size conditions for sparse Gaussian designs and for sparsified dense designs. It makes the sampling–computation trade-off explicit and gives recovery guarantees under strong active sparsification.
- 1. Introduction.: The paper asks how measurement sparsity trades off against sampling complexity, noting that sparse measurements reduce storage and computation but require more samples.The motivating applications include compressive sensing, sparse regression, denoising, and related signal-recovery tasks.
- 1.1. Sparse measurement setting.: In the high-SNR regime ds/p → ∞, the MLE recovers the support once the sample size exceeds the paper’s sufficient threshold.The result concerns binary sparse signals and uses a Chernoff bound followed by a union bound over competing supports.
- 1.1. Sparse measurement setting.: Combining sufficiency with prior necessary conditions yields an information-theoretic phase transition and a price of sparsity Γ = log s/log(ds/p).The price is the factor by which restricting each measurement to d nonzeros inflates the required sample size relative to dense measurements; it becomes negligible when s = Θ(p) and d = Θ(p).
- 1.2. Active Sparsification.: The paper also studies active sparsification, where dense observations are estimated with an independently sparsified design and rescaled response in the regime s = αp and d = ψp.Theorem 3 guarantees support recovery up to any fixed error fraction δ for sufficiently small fixed ψ, given a sufficiently large sample size.
- 1.2. Active Sparsification.: For active sparsification, the additional sampling cost is attributed to bias from naïvely rescaling observations rather than to measurement sparsity itself.The sparsified observations retain information from nullified components of the original design, creating the stated bias.
- 1.2. Active Sparsification.: The strong-sparsification guarantee supports a sparsification budget: with n = Ω(p), recovery holds when ψ is at least a constant multiple of √(p/n).Equivalently, a practitioner may zero out all but an order-√(p/n) fraction of design entries per row while retaining recovery guarantees.
2. Sparse Recovery using Sparse Measurements.
This section derives sufficient sample-size conditions for MLE support recovery with sparse Gaussian measurements and identifies the resulting information-theoretic price of measurement sparsity.
- Sparse measurement recovery: Theorem 1 gives sufficient conditions for reliable MLE recovery when d = o(p) and ds = ω(p), corresponding to high SNR.The proof uses large-deviation bounds on high-error supports followed by a union bound.
- Sparse measurement recovery: The sparse-recovery threshold is of order s log(p/s) / log(ds/p), with an additive term depending on δ and σ².
- Phase transition: Combining sufficiency with prior necessary conditions yields an information-theoretic phase transition: below the threshold reliable recovery is impossible, while above it the MLE recovers asymptotically.The impossibility and sufficiency statements concern different recovery notions.
- Price of sparsity: The price of sparsity is a multiplicative sample-complexity factor greater than one that increases as the measurement density d/p decreases.For s = p^α and d = p^β, the factor is Γ = α/(α + β − 1).
- Sampling–computation trade-off: In a linear-sparsity example, sparse measurements increase sample complexity by at most a logarithmic factor while reducing support-recovery computation by nearly a linear factor in p.The computational reduction follows from cheaper matrix-vector multiplication with sparse measurements.
- Computational scope: The information-theoretic guarantee tolerates d = ω(1), weaker than the polynomial growth condition associated with prior polynomial-time recovery guarantees.This broader regime may entail super-polynomial computational complexity because the MLE is generally exponential-time.
3. Sparse Recovery via Active Sparsification.
The paper studies support recovery when dense Gaussian measurements are independently sparsified for estimation and the response is rescaled. In the proportional regime, it proves recovery for sufficiently small fixed sparsification rates with sample size scaling as p/ψ^2.
- 3.1. Setup: The observations come from the original dense design, while estimation uses an independently sparsified design and a rescaled response.
- 3.2. Results.: Theorem 3 establishes a sufficient sample-size condition for reliable support recovery after sparsifying an originally dense measurement matrix.
- 3.2. Results.: A sample size of order p/ψ^2 suffices for support recovery when s = αp and d = ψp, for any fixed target error and slack.The guarantee applies for sufficiently small fixed ψ.
- 3.2. Results.: The sparsification price reflects information loss from bias introduced by naïvely rescaling observations that retain contributions from nullified dense-design components.
- 3.2. Results.: The theorem applies only when n = Ω(p), below which its stated guarantee does not hold.
4. Sparse Recovery using Sparse Measurements: Proofs.
The proofs establish sufficient and necessary recovery thresholds for sparse Gaussian measurements in the high-SNR regime. Together, they identify an information-theoretic transition and expose the trade-off between measurement sparsity, sample complexity, and computation.
- 4.1. Sparse recovery proofs: The proof analyzes row-wise loss differences using moment-generating functions, Chernoff bounds, and a union bound over supports with sufficiently large symmetric difference.
- 4.1. Linear regime: In the proportional regime, the sufficient threshold depends on log d, while the computational cost of matrix-vector multiplication is lower for sparse measurements.
- 4.3. Interpretation: The resulting phase transition makes the price of measurement sparsity explicit and reveals a trade-off between sampling complexity and computational cost.
5. Sparse Recovery via Active Sparsification: Proof of Theorem 3.
The proof of Theorem 3 controls recovery errors under active sparsification through conditional Gaussian moment-generating functions and a regularized Chernoff parameter. Concentration of sparsification masks and a support-union bound then yield the stated sufficient condition.
- 5.1. Proof strategy: The proof combines a conditional Chernoff bound with a union bound over supports whose relative error is at least δ.
- 5.1. Conditional MGF: The conditional row MGF depends on sparsification-mask sums over the missed, falsely included, and correctly shared support components.The relevant Gaussian variances and covariance are explicit functions of these mask sums.
- 5.2. Regularization: A shrinkage factor λ < 1 keeps the Gaussian-product MGF finite uniformly, at the cost of a controlled degradation absorbed by the slack ε.
- 5.3. Uniform control: Concentration of the mask sums around their mean profile enables a uniform large-deviation estimate over all competing supports.
6. Conclusion and Future Work.
The paper establishes recovery guarantees for both intrinsically sparse measurements and sparsified dense measurements. It concludes that sufficiently strong sub-proportional sparsification may make recovery impossible, a regime left for future work.
- Sparse measurements: For sparse measurements, the high-SNR condition ds/p → ∞ yields an information-theoretic phase transition and an explicit trade-off involving measurement sparsity.
- Sparsified dense measurements: For sparsified dense measurements with s = αp and d = ψp, recovery is guaranteed for sufficiently small fixed ψ when the sample size exceeds Theorem 3’s threshold.
- Future work: The paper conjectures that recovery is information-theoretically impossible for sub-proportional sparsification d = o(p), regardless of sample size.
A.1. Omitted Proofs from Theorem 1.
The omitted proofs establish concentration and Gaussian characteristic-function bounds used in Theorem 1. Their error terms become small when ds/p exceeds a sufficiently large threshold T.
- A.1. Omitted Proofs from Theorem 1.: The appendix introduces proofs of Lemmas 4.1 and 4.2, including a characteristic-function argument for the former.The supplied excerpts do not include the full displayed definitions or derivations.
- A.1.2. Proof of Lemma 4.2: Lemma 4.2 splits according to the event E_p defined by a lower bound on N_p and controls its complement using a binomial lower-tail deviation.The proof invokes a multiplicative Chernoff bound for Σ_p.
- A.1.2. Proof of Lemma 4.2: The deterministic bound in Lemma 4.2 converges to 2δ, yielding V_p ≤ 2σ divided by an omitted expression for sufficiently large p.The supplied passage states that the bound is at least δ for all p ≥ p1.
- A.1.1. Proof of Lemma 4.1: The proof of Lemma 4.1 bounds Ξ2 by T e^(-T/2) when ds/p > T > 2.The bound follows from the monotonicity of x ↦ √x e^(-√x/2).
- A.1.1. Proof of Lemma 4.1: The resulting right-hand side is independent of p and tends to zero as T approaches infinity.The first term vanishes once T exceeds a condition involving σ.
A.2.1. Derivation of the conditional row moment generating function.
The derivation rewrites the first-row likelihood difference as a product of Gaussian-linear terms, isolates the noise contribution, and integrates it out conditionally.
- A.2.1. Derivation of the conditional row moment generating function: The first-row expansion expresses Δ1 as W(2ψD − R) + 2ψWZ.This follows by factoring a difference of squares and using the inner-product difference equal to −W.
- A.2.1. Derivation of the conditional row moment generating function: Integrating over Z after conditioning on (X1, B1) handles the only term in the exponent that contains the Gaussian noise variable.The noise is specified as Z ∼ N(0,σ^2).
- A.2.1. Derivation of the conditional row moment generating function: After defining Uθ := θW and Vθ := R − 2ψD + γ(θ)W, the exponent becomes UθVθ.This product is identified with equation (31).
- A.2.1. Derivation of the conditional row moment generating function: The derivation regroups Vθ by index set to match the definitions used in Section 5.The supplied passage identifies this regrouping but does not reproduce the resulting display.
- A.2.1. Derivation of the conditional row moment generating function: Conditionally on B1, Uθ and Vθ are centered and jointly Gaussian because both are linear in the Gaussian vector X1.Their coefficients are determined by the mask B1.
A.2.2. Conditional variances and covariance of the Gaussian pair.
The appendix computes conditional second moments of the Gaussian pair and evaluates its product-exponential moment through a determinant condition, including degenerate covariance cases.
- A.2.2. Conditional variances and covariance of the Gaussian pair: Conditionally on the mask, Uθ and Vθ are centered jointly Gaussian, with second moments obtained by summing coefficient products over disjoint sets A, B, and C.The coefficient formulas depend on the binary mask entries b_j.
- A.2.2. Conditional variances and covariance of the Gaussian pair: The Uθ coefficients are θb_j on A, −θb_j on B, and zero on C, while Vθ has the corresponding set-specific coefficients.These coefficients determine the subsequent variance and covariance calculations.
- A.2.2. Conditional variances and covariance of the Gaussian pair: The covariance calculation receives contributions only from A and B because the Uθ coefficient vanishes on C.The variance calculation sums squared coefficients and uses |A| + |C| = s.
- A.2.2. Conditional variances and covariance of the Gaussian pair: For a positive-definite covariance matrix, the Gaussian quadratic-form MGF formula applies exactly when D = (1 − c)^2 − ab > 0.The determinant calculation shows det(I − ΣJ) = D.
- A.2.2. Conditional variances and covariance of the Gaussian pair: In degenerate cases, the product UV is either identically zero or a scalar multiple of a squared Gaussian variable, and E[e^(UV)] = D^(-1/2) remains valid.For the boundary cases, D = 1 or the same positivity condition is recovered.