Abstract
Compressed sensing (CS) enables the reconstruction of high-resolution signals from a limited set of measurements, provided the signal is sparse in a transform domain. This paper introduces the Sparsity Averaging Reweighted Analysis (SARA) algorithm, which leverages the observation that natural images are simultaneously sparse across multiple wavelet frames. By employing a reweighted $\ell_1$ minimization approach on a concatenated dictionary of Daubechies bases, SARA significantly improves reconstruction quality and reduces visual artifacts compared to standard Total Variation (TV) and single-basis methods.
Introduction
In the field of Compressive Imaging, the goal is to reconstruct a signal from a small number of measurements. This is traditionally achieved by exploiting signal sparsity in a single basis (e.g., wavelets) or the gradient domain (Total Variation). However, natural images are complex; sharp edges may be sparse in one domain, while textures are better represented in another.
We propose that picking a single "best" basis is insufficient. Instead, SARA exploits the fact that images exhibit sparsity across many different frames simultaneously. By promoting "average sparsity" across a redundant dictionary, we can achieve more robust and accurate reconstructions.
Methodology
The SARA algorithm is built on three core pillars:
- Redundant Dictionary: The authors concatenate the first eight Daubechies wavelet bases (Db1-Db8) into a single redundant dictionary. Interestingly, the coherence (similarity) between these frames is found to be a feature that strengthens the average sparsity prior.
- Analysis Formulation: Unlike synthesis methods that build images from atoms, SARA uses an analysis approach, evaluating the coefficients produced when the image is projected onto the dictionary.
- Reweighted $\ell_1$ Minimization: To approximate the computationally difficult $\ell_0$ norm (the true measure of sparsity), SARA uses a sequence of weighted $\ell_1$ problems. Weights are updated iteratively to be the inverse of previous coefficients, effectively pushing small coefficients toward zero and suppressing noise.
The underlying convex optimization problem is solved efficiently using the Douglas-Rachford splitting proximal algorithm.
Experimental Results
SARA was evaluated against standard benchmarks, including the Lena image and MR brain scans. Quantitative results demonstrate that SARA consistently outperforms state-of-the-art methods like TV, BPDb8, and Curvelets, as well as their reweighted counterparts.
As shown in the performance plots, SARA achieves SNR gains between 0.9 and 1.9 dB over the next best methods across various undersampling ratios. It also maintains superior performance as measurement noise increases.
Qualitatively, SARA reconstructions show a dramatic reduction in artifacts. While TV often produces "cartoon-like" blocky images due to its piecewise-smoothness prior, SARA preserves fine details and textures much more naturally.
Conclusion
SARA demonstrates that average sparsity across multiple frames is a powerful prior for compressive imaging. By bridging the gap between $\ell_1$ and $\ell_0$ norms through reweighting, the algorithm effectively "zeros out" artifacts while preserving essential image features. Future work will explore theoretical sampling bounds for concatenated frames and investigate the computational optimization of these redundant dictionaries.
Summary updated