Source-linked AI summary
Information theoretic bounds for Compressed Sensing
Shuchin Aeron, Venkatesh Saligrama, Manqi Zhao
TL;DR
The paper asks how many noisy compressed measurements are required to recover sparse signals under support or mean-squared distortion. It derives converse and achievability bounds using Fano inequalities, ML analysis, and rate-distortion theory, finding sharp output-noise requirements and Bayesian distortion tradeoffs.
Problem
The paper studies how measurements and SNR must scale with sparsity, dimension, and distortion for reconstruction under output and input noise.
Method
It combines Fano-type converse bounds, maximum-likelihood analysis based on a superposition property, and Bayesian rate-distortion arguments.
Results
For worst-case output noise, exact support recovery requires SNR = Ω(log(n)) and m = Ω(k log(n/k)); approximate recovery can suffice with constant SNR in the linear regime.
Takeaways & Limitations
The bounds are order-wise tight and characterize tradeoffs between measurements, SNR, and distortion, including Bayesian mean-squared recovery.
Takeaways & Limitations
The input-noise model is motivated by noisy observations compressed in sensor-network fusion, while support results also assume nonzero support amplitudes are bounded away from zero.
Abstract
from arXiv · showhide
In this paper we derive information theoretic performance bounds to sensing and reconstruction of sparse phenomena from noisy projections. We consider two settings: output noise models where the noise enters after the projection and input noise models where the noise enters before the projection. We consider two types of distortion for reconstruction: support errors and mean-squared errors. Our goal is to relate the number of measurements, $m$, and $\snr$, to signal sparsity, $k$, distortion level, $d$, and signal dimension, $n$. We consider support errors in a worst-case setting. We employ different variations of Fano's inequality to derive necessary conditions on the number of measurements and $\snr$ required for exact reconstruction. To derive sufficient conditions we develop new insights on max-likelihood analysis based on a novel superposition property. In particular this property implies that small support errors are the dominant error events. Consequently, our ML analysis does not suffer the conservatism of the union bound and leads to a tighter analysis of max-likelihood. These results provide order-wise tight bounds. For output noise models we show that asymptotically an $\snr$ of $Θ(\log(n))$ together with $Θ(k \log(n/k))$ measurements is necessary and sufficient for exact support recovery. Furthermore, if a small fraction of support errors can be tolerated, a constant $\snr$ turns out to be sufficient in the linear sparsity regime. In contrast for input noise models we show that support recovery fails if the number of measurements scales as $o(n\log(n)/SNR)$ implying poor compression performance for such cases. We also consider Bayesian set-up and characterize tradeoffs between mean-squared distortion and the number of measurements using rate-distortion theory.
1 Introduction
The paper develops information-theoretic bounds for reconstructing sparse signals from noisy compressed measurements, covering support and mean-squared distortions under output and input noise. It combines converse bounds with maximum-likelihood and rate-distortion analyses to characterize measurement and SNR requirements.
- Scope: The framework relates measurements m and SNR to sparsity k, distortion d, and dimension n for noisy compressed sensing.It studies both support distortion and mean-squared distortion, which respectively assess support detection and support plus amplitude estimation.
- Exact and approximate support recovery: Output noise requires SNR = Ω(log(n)) and m = Ω(k log(n/k)) for exact support recovery.These conditions are presented as necessary and sufficient in the stated worst-case setting.
- Exact and approximate support recovery: Constant SNR suffices in the linear sparsity regime when a constant fraction of support errors is tolerated.Approximate recovery therefore permits a tradeoff among measurements, SNR, and support distortion.
- Methods: The analysis uses Fano-type inequalities for necessary conditions and a superposition property in ML analysis to show that small support errors dominate.This avoids the conservatism of a union bound and yields order-wise tight conditions.
- Bayesian recovery: Bayesian recovery characterizes measurement–distortion tradeoffs through general rate-distortion functions.The sufficient analysis uses covering properties and minimum-distance decoding over rate-distortion quantization points.
2 Problem Set-up
The problem setup defines sparse signals, noisy sensing models, distortion, and sensing capacity for asymptotic reconstruction analysis. Sensing capacity measures the source information conveyed per measurement at a target distortion.
- Signal and sensing models: The paper considers output and input noise models with deterministic or stochastic sparsity and compression matrices.For stochastic sensing, the matrix is drawn from an IID Gaussian ensemble; deterministic columns are normalized.
- Signal models: Signals have support size at most k, with sparsity ratio α_n = k/n.A bounded-away-from-zero subclass requires every nonzero support component to have magnitude at least β > 0.
- Signal models: The β > 0 condition is necessary for support recovery because arbitrarily small nonzero components cannot be distinguished under noisy measurements.This assumption defines a restricted sparse-signal family used in support-recovery results.
- Asymptotic formulation: The analysis is asymptotic, letting n and k grow at different rates while bounding measurements m and SNR for exact or approximate reconstruction.It also considers reconstruction of functions such as the support or sign of X.
- Sensing capacity: Constant sensing capacity means measurements scale proportionally with source entropy, whereas vanishing capacity indicates poor compression.The support entropy is measured through nH2(k/n).
- Sensing capacity: Sensing capacity is the largest source-information rate per measurement for which an estimator achieves distortion at most d0 with probability approaching one.Capacity depends explicitly on SNR, the sparsity sequence, and the target distortion.
3 Support Recovery: Worst-Case Setting
The paper characterizes necessary and sufficient conditions for exact and approximate support recovery under output and input noise. Output noise permits compressed recovery under logarithmic SNR and near-optimal measurements, whereas input noise can eliminate meaningful compression.
- Exact support recovery requires SNR = Ω(log(n)); with SNR = O(log(n)), it is impossible when m = o(k log(n/k)).These are necessary conditions for the output noise model.
- The ML sufficiency analysis relies on support errors larger than one being contained in unions of single-support-error events, a relation largely preserved by well-conditioned compression.This superposition property focuses the analysis on small support errors rather than applying a conservative union bound over all errors.
- For input noise, recovery fails under the theorem’s scaling condition, and meaningful compression is unavailable in noisy regimes.Support recovery requires either SNR scaling linearly with n or measurements scaling linearly with n.
- With a constant fraction of support errors tolerated, constant SNR suffices for approximate recovery in the linear sparsity regime.The result applies to output noise and allows a fixed support distortion level.
4 Recovery for Arbitrary Distortions: Bayesian signal model
The Bayesian analysis derives distortion-dependent recovery bounds using rate-distortion covers, modified Fano inequalities, and minimum-distance decoding. For squared distortion, ML decoding over quantization points yields a constructive upper bound on reconstruction error.
- The analysis develops lower and upper probability-of-error bounds for reconstruction subject to a prescribed distortion.Lower bounds modify Fano’s inequality to identify the correct rate-distortion quantization point; upper bounds use minimum-distance decoding.
- Rate-distortion covering maps signals to quantization points while keeping reconstruction distortion below d0 with high probability.The cover uses exponentially many distortion balls, with the scalar rate-distortion function determining their count.
- The constructive estimator maps Y to the nearest projected quantization point GZi and outputs its associated quantization point Zi.This is a modified maximum-likelihood rule for the Bayesian output-noise model.
- For squared distortion, pairwise errors compare distortion balls whose minimum squared separation is at least 2nd0.The AWGN analysis projects noise onto the direction joining projected quantization points and bounds the resulting pairwise error.
- A union bound over non-neighboring rate-distortion points produces the overall reconstruction-error upper bound.The number of competing quantization points is controlled by the rate-distortion function.
5 Approximate Recovery: Bayesian Bounds
The Bayesian bounds specialize rate-distortion analysis to sparse binary and mixture models under output and input noise. They characterize necessary and sufficient measurement and SNR conditions for Hamming and ℓ2 distortion, while exposing measurement–distortion tradeoffs.
- Bayesian models: The Bayesian model uses IID mixture components, including approximately k=αn sparse binary sequences and continuous-valued sparse signals.The binary case supports Bayesian support-recovery analysis, while the mixture model also supports ℓ2 distortion results.
- Hamming distortion: For input noise, recovery within Hamming distortion d0 requires m to exceed a rate-distortion-dependent threshold, while smaller m cannot suffice.The necessary and sufficient conditions are stated through nRX(d0), αβ^2SNR, and the constructive ML estimator.
- Hamming distortion: For output noise, insufficient measurements and SNR prevent recovery within average Hamming distortion d0.The necessity condition depends on nRX(d0) and the logarithmic SNR expression in Theorem 5.2.
- Tradeoffs: Allowing distortion creates a measurement tradeoff: larger admissible distortion can reduce the required number of measurements, including for input-noise models.The paper notes that this differs from exact support recovery, where measurement requirements can grow with signal dimension.
- ℓ2 distortion: Analogous necessary and sufficient bounds are derived for average ℓ2 distortion under both output and input noise models.The bounds are expressed using rate-distortion terms and the corresponding logarithmic SNR factors.
6 Appendix
The appendix develops worst-case support-error bounds by grouping signals according to support and analyzing competing support hypotheses. Projection geometry and minimum singular values control the resulting error events.
- Signals are grouped into equivalence classes having the same support, creating a one-to-one correspondence with binary k-sparse sequences.
- The proof lower-bounds worst-case support error through events in which an incorrect support is more likely than the true support.
- The proof simplifies support-error events by optimizing over unknown signal amplitudes and replacing the resulting terms with Gaussian noise tail bounds.It then applies a union bound over possible locations and amplitudes.
- Projection operators and minimum singular values reduce the error analysis to geometric separation between competing support subspaces.The argument uses positivity of a projection-related matrix term and controls the geometry through σmin((G′)T G′).
- If a column of G′ lies in the null space of the true-support matrix, the worst-case error probability is one; full rank with m ≥2k + 1 prevents this event.
7 Proof of Lemma 3.6
The proof bounds support-error probabilities by reducing competing events to Gaussian projections and applying a union bound over possible error locations and amplitudes.
- The analysis represents the relevant random term as a normalized Gaussian projection involving W and the covariance-weighted sensing direction.
- A union bound over 2n error events combines the location choices with the two candidate amplitudes X=±β/2.
- The Gaussian tail is bounded using Q(x)≤exp(−x^2/2), yielding an exponential control on each error event.
8 Proof of Lemma 3.7
The proof develops a rate-distortion argument for reconstruction under a distortion constraint and extends support-error bounds by relating larger errors to smaller error events. It also states that the Gaussian-matrix result follows the preceding development.
- Support-error analysis: Support-error events with Hamming distortion at least 2kd0 + 1 are almost contained in events with kd0 ≤ dH ≤ 2kd0.This modifies the upper bound used in the deterministic-case analysis.
- Gaussian case: The Gaussian G result is identical to the development in Section 3.3.
- Rate-distortion argument: The conditional-entropy expansion separates the error and no-error cases using the probability Pe of the defined error event.The bound includes H(f(Xn)|Y, En = 1) and H(f(Xn)|Y, En = 0).
- Rate-distortion argument: The rate-distortion proof lower-bounds conditional uncertainty using data processing over f(Xn) ↔ Xn ↔ Y.The argument uses H(f(Xn)|Y) ≥ H(f(Xn)) − I(Xn;Y).
- Rate-distortion argument: The proof connects the rate-distortion function to the covering quantity through I(f(Xn); Xn) ≥ nRX(d0) and K(n,d0) = 1.
- Gaussian-mixture specialization: For a Gaussian-mixture source, the rate-distortion function is specified piecewise over a distortion range involving σ0, σ1, and mixture ratio α.