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.
Introduction
Compressed Sensing (CS) traditionally promises that sparse signals can be recovered from far fewer measurements than the Nyquist rate suggests. However, real-world systems are inherently noisy. This work addresses the gap between idealized CS theory and practical constraints by establishing the fundamental "speed limits" of sensing capacity. The authors explore two distinct noise scenarios: Output Noise, where noise is added after the sensing matrix is applied, and Input Noise, where the signal itself is noisy before compression.
Methodology
The authors employ a rigorous information-theoretic framework to derive both necessary and sufficient conditions for reconstruction:
- Fano’s Inequality: Used to establish necessary conditions (lower bounds), proving when reconstruction is mathematically impossible.
- Maximum-Likelihood (ML) Analysis: To establish sufficient conditions (upper bounds), the authors analyze an ML decoder. They introduce a "superposition property" showing that large support errors are composed of single-element errors, allowing for tighter bounds than standard union-bound approaches.
- Rate-Distortion Theory: In the Bayesian setup, the number of measurements is linked directly to the rate-distortion function of the sparse source, treating the sensing matrix as a form of source coding.
Key Results and Insights
Exact Support Recovery
For exact support recovery in the presence of output noise, the results show that the SNR must scale with $\log(n)$. This indicates a hard floor: low SNR cannot be compensated for simply by increasing the number of measurements. The necessary and sufficient conditions are found to be $m = \Theta(k \log(n/k))$ and $SNR = \Theta(\log n)$.
The Input Noise "Compression Killer"
A striking insight of this work is the pessimism regarding input noise. If noise enters before the sensing matrix, the number of measurements $m$ must scale almost linearly with the full dimension $n$. Specifically, recovery fails if $m = o(n \log n / SNR)$, suggesting that for applications like noisy sensor networks, random projections offer very poor compression performance compared to noiseless settings.
Approximate Support Recovery
While exact recovery requires $\log(n)$ SNR, the authors demonstrate that if a small, constant fraction of support errors can be tolerated, a constant SNR (independent of $n$) is sufficient in the linear sparsity regime.
Conclusion
This research provides order-wise tight bounds on sensing capacity, highlighting the critical difference between input and output noise models. While CS remains efficient for output noise, its utility is severely hampered by input noise. Furthermore, the analysis reveals that approximate recovery allows for significantly more relaxed SNR requirements compared to exact recovery, providing a theoretical foundation for practical, noise-tolerant sensor network design.
Summary updated