Abstract
In this paper, we study recovery conditions of weighted $\ell_1$ minimization for signal reconstruction from compressed sensing measurements when partial support information is available. We show that if at least 50% of the (partial) support information is accurate, then weighted $\ell_1$ minimization is stable and robust under weaker conditions than the analogous conditions for standard $\ell_1$ minimization. Moreover, weighted $\ell_1$ minimization provides better bounds on the reconstruction error in terms of the measurement noise and the compressibility of the signal to be recovered. We illustrate our results with extensive numerical experiments on synthetic data and real audio and video signals.
Introduction
Compressed sensing (CS) has revolutionized signal processing by allowing the reconstruction of sparse signals from significantly fewer measurements than required by the Nyquist-Shannon sampling theorem. The standard approach, $\ell_1$ minimization, is non-adaptive and treats all signal entries equally. However, in many practical scenarios—such as medical imaging or video processing—prior information about the signal's support (the locations of non-zero entries) is often available. This paper investigates how to effectively incorporate such partial and potentially inaccurate information to enhance recovery performance.
Weighted $\ell_1$ Minimization
The authors propose a weighted $\ell_1$ minimization framework: $$\text{minimize } \|z\|_{1,w} \text{ subject to } \|Az - y\|_2 \le \epsilon$$ In this formulation, weights $w_i$ are set to a small value $\omega \in [0, 1]$ for indices within an estimated support $\tilde{T}$, and $w_i = 1$ elsewhere. This approach allows the recovery process to "favor" certain indices based on prior knowledge.
Theoretical Insights: The 50% Threshold
A central finding of this work is the identification of a critical accuracy threshold. If the support estimate is more than 50% accurate ($\alpha > 0.5$), weighted $\ell_1$ minimization is theoretically guaranteed to outperform standard $\ell_1$ minimization.
As shown in the figure above, when $\alpha > 0.5$, the allowable RIC increases as the weight $\omega$ decreases. This implies that the measurement matrix $A$ can be less "perfect" while still ensuring stable recovery. Conversely, if the estimate is poor ($\alpha < 0.5$), standard $\ell_1$ ($\omega=1$) remains the safer choice.
Furthermore, the error constant for noise ($C_0$) decreases as $\omega$ is reduced for accurate support estimates. This leads to tighter reconstruction error bounds, making the process more robust to measurement noise. The choice of $\omega$ also serves as a "safety net." While $\omega=0$ is optimal for perfectly accurate support estimates, using a small non-zero weight (e.g., $\omega=0.1$) acts as a regularizer, preventing the algorithm from being overly biased by inaccurate priors in practical applications.
Experimental Validation
The theoretical findings were validated across several datasets:
- Synthetic Signals: Confirmed the predicted recovery limits and the benefits of the 50% accuracy threshold.
- Video Sequences: Using the "Foreman" sequence, weighted $\ell_1$ achieved a 1 dB improvement in Peak Signal-to-Noise Ratio (PSNR) over standard $\ell_1$ by leveraging motion-compensated support estimates.
- Speech Signals: Experiments on real audio showed that an intermediate weight $\omega$ (typically 0.3 to 0.5) maximized the Signal-to-Noise Ratio (SNR), balancing the use of low-frequency priors with the inherent compressibility of speech.
Conclusion
Weighted $\ell_1$ minimization provides a robust and theoretically sound method for incorporating prior support information into compressed sensing. By relaxing the requirements on the measurement matrix and improving error bounds, this approach significantly enhances the reconstruction of real-world signals like audio and video, especially when at least half of the prior information is reliable.
Summary updated