Information theoretic bounds to performance of Compressed Sensing and Sensor Networks

Shuchin Aeron, Manqi Zhao, Venkatesh Saligrama

Abstract

This paper establishes fundamental information-theoretic limits for the reconstruction of sparse signals from noisy projections. By analyzing both output and input noise models, the authors derive necessary and sufficient conditions for reconstruction under two primary distortion metrics: support errors and mean-squared error (MSE). Utilizing an extended version of Fano's inequality and a novel Maximum Likelihood (ML) analysis based on a superposition property, the research provides order-wise tight bounds that clarify the relationship between measurement count ($m$), signal-to-noise ratio (SNR), and signal sparsity ($k$).

Introduction

Compressed Sensing (CS) has revolutionized signal processing by demonstrating that high-dimensional sparse signals can be reconstructed from a relatively small number of linear measurements. However, a critical question remains: what are the absolute physical limits of this reconstruction? Moving beyond specific algorithmic performance (like $\ell_1$-minimization or LASSO), this work seeks to define the "algorithm-independent" boundaries of SNR, measurement count ($m$), and sparsity ($k$) beyond which no reconstruction method can succeed.

Problem Formulation and Analysis Framework

The study addresses two main settings: Output Noise Models, where noise is introduced after the projection, and Input Noise Models, where noise is present in the signal before projection (common in Sensor Networks). Performance is evaluated using two distortion metrics: Support Errors (failure to identify non-zero indices) and Mean-Squared Error (the numerical distance between the original signal and its estimate).

To find these fundamental limits, the authors "sandwich" the truth between lower and upper bounds using two primary mathematical frameworks:

  • Necessary Conditions (Lower Bounds): The researchers extended Fano’s Inequality to accommodate continuous signal sources and approximate reconstructions. This provides the thresholds below which the probability of error is guaranteed to be high regardless of the algorithm used.
  • Sufficient Conditions (Upper Bounds): The authors analyzed the Maximum Likelihood (ML) decoder. While ML is often computationally intractable, it serves as the theoretical gold standard for performance.
Overview of the research objectives and the information-theoretic tools developed to analyze distortion metrics.

The Superposition Insight

A key innovation in this analysis is the Superposition Property. Traditional analyses often rely on conservative "union bounds" that overestimate error probabilities. The authors discovered that in support recovery, the dominant error events are "small"—missing only one or two indices. By focusing on these specific events, they derived much tighter sufficient conditions than previous literature, proving that ML decoding is far more powerful than previously thought.

Key Results

The paper reveals several critical transitions in the performance of CS systems:

  1. Exact Support Recovery (CS): For a signal of dimension $n$ and sparsity $k$, the authors show that $m \approx 6k \log(n/k)$ measurements and an $SNR \approx \log(n)$ are both necessary and sufficient.
  2. The SNR "Cliff": For exact recovery, the SNR must scale with $\log(n)$. However, if a small fraction of errors is acceptable, a constant SNR becomes sufficient in the linear sparsity regime ($k = \alpha n$).
  3. Linear Sparsity Regime: In cases where sparsity grows linearly with dimension, the authors' ML analysis provides much sharper bounds than existing LASSO analysis, as shown in the table below.
Comparison of the derived ML bounds against standard LASSO performance across different sparsity regimes.
  1. Sensor Networks (SNETs) vs. CS: A subtle difference in matrix normalization (columns vs. rows) leads to a stark performance gap. In SNETs, the number of measurements may need to scale with the total dimension $n$ rather than the sparsity $k$, significantly reducing compression efficiency.

Conclusion and Future Work

This work provides a rigorous framework for understanding the limits of sparse signal reconstruction. By identifying that small support errors are the primary bottleneck and characterizing the trade-offs between SNR and distortion, the authors offer a roadmap for designing more efficient sensing systems. While the ML decoder remains a theoretical benchmark due to its NP-hard complexity, these bounds provide a target for future algorithmic development and highlight the inherent challenges in sensor network environments. Future directions include refining the sub-linear sparsity regime for $\ell_2$ distortion using more complex signal mixtures.

Summary updated

Abstract

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 $\Theta(\log(n))$ together with $\Theta(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.
BibTeX
@misc{aeron2008information,
  author = {Shuchin Aeron and Manqi Zhao and Venkatesh Saligrama},
  title = {{Information theoretic bounds to performance of Compressed Sensing and Sensor Networks}},
  year = {2008},
  eprint = {0804.3439},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0804.3439},
}
Figure