Source-linked AI summary
Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices
Wei Wang, Martin J. Wainwright, Kannan Ramchandran
TL;DR
The paper asks for information-theoretic limits on exact support recovery from noisy measurements when signal and measurement dimensions scale jointly. It derives sharper necessary conditions for general dense ensembles and lower bounds for γ-sparsified ensembles. The results characterize dense recovery sharply in important regimes and identify three regimes in which measurement sparsity has no, minor, or dramatic effects on statistical efficiency.
Problem
Existing support-recovery limits must account for both general measurement ensembles and the trade-off between sparse-matrix efficiency and statistical efficiency.
Method
The paper analyzes necessary conditions for arbitrary decoders using general dense measurement matrices and γ-sparsified Gaussian ensembles across jointly scaling parameters.
Results
The dense analysis gives sharp recovery characterizations in key sparsity regimes, while the sparsified analysis identifies three measurement-sparsity regimes affecting information-theoretic limits.
Takeaways & Limitations
Measurement sparsity can reduce storage, computation, communication cost, and latency, but may require more observations for reliable support recovery.
Takeaways & Limitations
Power-based SNR is not suitable for support recovery: it can become arbitrarily large while recovery remains arbitrarily difficult as βmin approaches zero.
Abstract
from arXiv · showhide
We study the information-theoretic limits of exactly recovering the support of a sparse signal using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations $n$, the ambient signal dimension $p$, and the signal sparsity $k$ are all allowed to tend to infinity in a general manner. This paper makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the sparsity $k$ and sample size $n$, including the important special case of linear sparsity ($k = Θ(p)$) using a linear scaling of observations ($n = Θ(p)$). Our second contribution is to prove necessary conditions on the number of observations $n$ required for asymptotically reliable recovery using a class of $γ$-sparsified measurement matrices, where the measurement sparsity $γ(n, p, k) \in (0,1]$ corresponds to the fraction of non-zero entries per row. Our analysis allows general scaling of the quadruplet $(n, p, k, γ)$, and reveals three different regimes, corresponding to whether measurement sparsity has no effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem.
1 Introduction
The paper studies information-theoretic limits for exact support recovery from noisy measurements, emphasizing how measurement-matrix sparsity trades statistical efficiency for computational and communication benefits. It develops sharper necessary conditions for dense ensembles and lower bounds for sparsified matrices across general signal and measurement scalings.
- Motivation: Dense Gaussian measurements can achieve information-theoretic efficiency, but their dense structure creates high storage and computational costs.Sparse matrices can also reduce communication cost and latency in distributed and streaming applications.
- Motivation: The central question is how measurement sparsity affects the trade-off between statistical efficiency and the cost of storing and manipulating measurements.Measurement sparsity is parameterized by γ, the fraction of nonzero entries per row.
- Contributions: The first contribution derives sharper necessary conditions for exact recovery under general dense measurement matrices, including non-Gaussian ensembles.Combined with prior sufficient conditions, these results characterize recovery across multiple sparsity regimes.
- Contributions: The second contribution derives observation lower bounds for γ-sparsified matrices while allowing signal dimension, sparsity, signal amplitude, and measurement sparsity to scale jointly.The analysis targets the consequences of sparsifying measurements for reliable exact recovery.
- Problem formulation: Exact support recovery asks when any decoder can identify the nonzero coordinates of a noisy k-sparse signal, regardless of computational complexity.The framework uses arbitrary decoders and asymptotically reliable recovery as the target.
- Contributions: The dense-ensemble analysis yields sharp necessary and sufficient conditions for linear sparsity k = Θ(p) with a linear fraction of observations n = Θ(p).The minimum nonzero signal magnitude βmin is identified as a key parameter for exact support recovery.
2 Main results and consequences
The paper derives sharper necessary conditions for support recovery with dense and γ-sparsified measurement ensembles, characterizing when recovery is information-theoretically possible. Dense ensembles yield tight results in several sparsity regimes, while sparsification produces three threshold regimes governed by γk.
- Dense ensembles: Gaussian channel-coding bounds are loose for general support recovery because signal power alone misses minimum coefficients and support overlap.The bound is tight for k = 1 with Gaussian measurements but loose in general.
- Dense ensembles: Theorem 1 gives necessary support-recovery conditions for i.i.d. zero-mean, unit-variance measurement ensembles, including non-Gaussian distributions.The proof uses Fano’s inequality and covers Gaussian and Bernoulli measurement matrices.
- Dense ensembles: When kβ^2_min = Θ(1), Θ(k log(p−k)) observations are necessary and sufficient, making the Lasso information-theoretically optimal.When kβ^2_min →∞ with linear sparsity, a gap remains between Lasso performance and information-theoretic bounds.
- Dense ensembles: In linear sparsity with n = Θ(p), the optimal decoder recovers exactly if and only if β^2_min = Ω(log(k)/k).This combines the necessary condition from Theorem 1 with a matching sufficient condition.
- Measurement sparsity: Theorem 2 derives γ-dependent necessary conditions for γ-sparsified Gaussian matrices, whose thresholds vary according to the scaling of γk.The analysis explicitly examines how sparsification changes the observation distribution.
- Measurement sparsity: If γk →∞, sparsification has no asymptotic effect; if γk = Θ(1), thresholds transition; and if γk →0 sufficiently fast, thresholds change fundamentally.The three regimes describe dense-like, transitional, and dramatically degraded recovery limits.
- Measurement sparsity: As γ decreases toward zero under the stated regime, the number of measurements required for reliable recovery increases dramatically.This identifies a severe information-theoretic cost of sufficiently sparse measurements.
3 Proofs of our main results
The proofs derive necessary conditions by reducing support recovery to restricted decoding problems and applying Fano’s inequality. Two restricted ensembles capture errors from many distant supports and fewer closely competing supports, with corresponding bounds for dense and sparsified measurements.
- Proof strategy: The proof framework gives the decoder side information, analyzes a restricted problem, and uses Fano’s inequality to lower-bound recovery error.This yields conditions under which every decoder’s error probability remains bounded away from zero.
- Restricted ensembles: The two restricted problems capture errors from many distant competing supports and from fewer closely overlapping supports.The second restriction can provide a tighter analysis in some regimes despite being an easier decoding problem.
- Restricted ensembles: Restricted ensemble A assumes all nonzero coefficients equal βmin while their support locations remain unknown.Knowing coefficient values cannot increase error, so this constructs a valid harder-instance lower bound for general recovery.
- Restricted ensembles: Restricted ensemble B reveals the k−1 largest nonzero locations and reduces recovery to locating the smallest nonzero among p−k+1 candidates.It targets confusable supports with overlap k−1.
- Dense measurements: For restricted ensemble B, average error remains bounded away from zero when n is below the displayed logarithmic threshold involving p−k+1 and βmin.The bound follows by combining a Fano lower bound with the information calculation.
- Sparsified measurements: For γ-sparsified Gaussian measurements, the proof averages Fano bounds over the matrix ensemble using entropy and covariance calculations for Gaussian mixtures.The resulting necessary conditions are obtained from bounds on the relevant mixture distributions and error probabilities.
4 Discussion
The discussion concludes that the paper sharpens information-theoretic support-recovery limits for dense measurements and characterizes how measurement sparsity affects statistical efficiency. It also identifies limitations of the sparsified result and an open question for sublinear sparsity.
- Discussion: Theorem 1 applies to zero-mean, unit-variance measurement entries and, with known sufficient conditions, sharply characterizes linear sparsity recovered using a linear observation fraction.Theorem 2 instead studies γ-sparsified Gaussian ensembles and identifies three regimes of measurement sparsity.
- Discussion: Theorem 1 implies that the standard Gaussian ensemble is information-theoretically optimal among zero-mean, unit-variance measurement distributions.The discussion states that no other such distribution reduces the observations needed for recovery.
- Discussion: For linear signal sparsity, Theorem 2 is not sharp, while its tightness for sublinear signal sparsity remains an open problem.This is the paper’s explicit scope limitation for the sparsified-measurement result.
A Proof of Lemma 1
The proof of Lemma 1 computes the covariance structure of observations under a uniformly random support and averages it over independent zero-mean, unit-variance measurement matrices.
- Covariance calculation: The proof represents the observations as a Gaussian mixture indexed by uniformly random support subsets.Conditioning on a support gives Gaussian observations with mean X_S β_S and covariance I.
- Covariance calculation: The covariance matrix of the observation vector is introduced through its mean and covariance under a fixed measurement matrix.The proof then averages this covariance over the measurement ensemble.
- Covariance calculation: Independence, zero mean, and unit variance of matrix entries determine the averaged covariance terms.The resulting calculation is summarized in Lemma 1.
- Combinatorial calculation: Counting supports by their overlap with a reference support supplies the combinatorial terms used to complete the lemma.Vandermonde’s identity is applied after reindexing the overlap parameter.
B Proof of Lemma 3
The proof of Lemma 3 analyzes the single-row observation distribution under γ-sparsified measurements as a Gaussian mixture indexed by the number of active measured coordinates.
- Mixture representation: For a fixed row, the number of nonzero entries among the k support coordinates follows L ∼ Bin(k, γ).Conditioning on L produces a mixture component for the row’s observation distribution.
- Mixture representation: Conditioned on the mixture label, the transformed variable has a noncentral chi-square distribution whose parameter depends on γ and the observation value.The moment-generating function is then used to obtain the desired quantity.
C Proof of Lemma 5
The proof expresses the entropy of Z through its conditional entropy given the binomial variable L and the mutual information between Z and L. Bounding the remaining conditional entropy yields matching upper and lower control via H(Z|L) and H(L).
- Entropy decomposition: L follows a Bin(k, γ) distribution, and the proof expands I(Z; L) in two equivalent ways.The expansion gives H(Z) − H(Z|L) = H(L) − H(L|Z).
- Conditional entropy: Because Z conditioned on L = ℓ is Gaussian, H(Z|L) can be evaluated using Gaussian conditional entropy.
- Entropy bounds: The bound 0 ≤ H(L|Z) ≤ H(L) converts the mutual-information identity into entropy bounds for Z.
- Entropy bounds: The resulting bounds are H(Z|L) ≤ H(Z) ≤ H(Z|L) + H(L).
D Proof of Lemma 6
The proof derives entropy bounds for binomial mixtures across three regimes determined by γk: at most one, constant, and greater than three. It combines binomial-expansion inequalities, median properties, Jensen’s inequality, and Gaussian entropy bounds.
- γk ≤ 1: The γk ≤ 1 case is handled by rewriting the binomial distribution and deriving matching bounds through binomial expansion inequalities.
- Entropy bounds: The inequality 1 + x ≤ e^x, together with e^−x ≤ 1 − x/2 for x ∈ [0, 1], supports the lower-bound derivation.
- γk = τ: For γk = τ, with τ constant, the upper-bound derivation remains valid and the lower-bound proof stops before its final inequality.
- γk > 3: For γk > 3, Jensen’s inequality supplies a bound using the binomial mean γk.
- Entropy bounds: An upper bound in the small-γk regime is 1/2 log(1 + kβ^2_min).
- γk ≤ 1: The lower-bound argument uses that a Bin(k, γ) median lies among {⌊γk⌋−1, ⌊γk⌋, ⌊γk⌋ + 1}.
E Bounds on binomial entropy
The binomial entropy is bounded by representing the count as a sum of independent Bernoulli variables and analyzing sparse-parameter asymptotics. A differential-entropy comparison gives a general explicit upper bound.
- General bounds: Writing L as the sum of k independent Ber(γ) variables yields H(L) ≤ kHbinary(γ).
- Sparse asymptotics: When γ = 1/(kf(k)) with f(k) → ∞, the first entropy term becomes log k/f(k) + log f(k).
- Sparse asymptotics: The condition γ → 0 holds if f(k) = ω(log k), while the second entropy term can also be expanded.
- Explicit bound: This bound follows by applying a differential-entropy bound on discrete entropy.