Abstract
This paper introduces the Sample Distortion (SD) function, a theoretical framework that quantifies the fundamental trade-off between sampling ratio and reconstruction error in Compressed Sensing (CS). By applying this framework to multi-resolution image models, the authors derive an optimal "reverse water-filling" strategy for sample allocation across wavelet bands. This approach significantly improves the quality of reconstructed natural images compared to standard uniform sampling, bridging the gap between empirical bandwise sampling and rigorous information-theoretic bounds.
Introduction
In traditional Compressed Sensing, homogeneous random sensing matrices are often considered the standard. However, natural images possess a highly structured multi-resolution nature, typically represented via wavelets where energy is concentrated in coarse scales and decays exponentially toward finer scales. While previous research attempted to tailor sensing matrices to this structure through empirical "bandwise sampling," a rigorous theoretical foundation was missing. Specifically, there was no clear way to determine the absolute minimum error achievable for a given number of samples or how to optimally distribute a limited "sampling budget" across different image scales.
Theoretical Framework: The Sample Distortion Function
The authors address these challenges by importing concepts from Information Theory into the CS domain. They define the Sample Distortion (SD) function, $D(\delta)$, which represents the minimum expected mean squared error (MSE) achievable at a specific sampling ratio $\delta$.
To establish performance limits, the authors derive two theoretical bounds:
- Entropy Based Bound (EBB): A sampling analogy to the Shannon bound.
- Model Based Bound (MBB): A tighter bound that accounts for specific signal distributions, such as Gaussian Mixtures.
A key insight is the requirement for the SD function to be convex. In scenarios where a specific decoder, such as the Belief Propagation-based Approximate Message Passing (BAMP), exhibits a concave region at low sampling rates, the authors introduce a "zeroing procedure." This involves sampling a portion of the signal at a higher, more reliable rate and ignoring the rest, effectively "convexifying" the performance and reducing overall error.
Optimal Sample Allocation via Reverse Water-Filling
For multi-resolution images, wavelet bands are treated as parallel sources. The authors derive an analytical sample allocation strategy that prioritizes bands with the highest "distortion reduction" potential. This strategy is analogous to "reverse water-filling" in transform coding, where resources are allocated to components that provide the most significant decrease in total distortion.
To further enhance performance, this sampling strategy is integrated with a Hidden Markov Tree (HMT) model within a Turbo-AMP framework. This integration allows the decoder to exploit inter-band dependencies—specifically, the fact that if a "parent" wavelet coefficient is large, its "children" are also likely to be significant.
Experimental Results
The proposed framework was evaluated using the Cameraman image for "oracle" performance and 200 images from the Berkeley Segmentation Dataset (BSD) to estimate average image statistics.
- Superior PSNR: The proposed Sample Allocation (SA) method consistently outperformed uniform sampling and other state-of-the-art methods by 1.5 to 2.0 dB in Peak Signal-to-Noise Ratio (PSNR) at low sampling ratios.
- Turbo-AMP Gains: When combined with the HMT structure, performance improved by an additional 0.5 to 1.5 dB, achieving state-of-the-art reconstruction quality.
- Predictive Power: The theoretical curves generated by the SD function matched empirical simulation results with high accuracy, providing a reliable tool for predicting performance before execution.
Conclusion
The SD framework provides both a design and predictive tool for Compressed Sensing. It reveals that for natural images with exponential energy decay, CS provides a constant factor improvement, while the rate of error decay remains dominated by the image's inherent smoothness. Future work includes finding the mathematically perfect sample allocation for Turbo-AMP systems that consider complex inter-band dependencies and refining predictions for smaller image patches where the "large system limit" assumption may be less accurate.
Summary updated