Abstract
In this paper, we propose a refined Dantzig selector based on the $\ell_{1}-\alpha \ell_{2}$ ($0 < \alpha \leq 1$) metric to improve sparse signal recovery. The Dantzig selector is particularly effective when the columns of the sensing matrix $\mathbf{A}$ are weakly correlated with the error vector $\mathbf{e} = \mathbf{A}\mathbf{x} - \mathbf{b}$. We establish recovery guarantees based on the Restricted Isometry Property (RIP) and propose an efficient ADMM-based algorithm to solve the non-convex model. Extensive numerical experiments demonstrate that the proposed model outperforms existing methods across Gaussian, impulsive, and uniform noise environments.
Introduction
Sparse signal recovery is a fundamental challenge in compressed sensing, where the goal is to reconstruct a signal $x \in \mathbb{R}^n$ from a limited set of noisy observations $b = Ax + e$. While the $\ell_0$ minimization problem directly targets sparsity, its NP-hard nature necessitates the use of proxies. The traditional Dantzig selector (DS) utilizes the $\ell_1$ norm as a convex surrogate, constrained by the correlation between the residual and the sensing matrix: $\|A^\top(b - Ax)\|_\infty \leq \eta$.
However, the $\ell_1$ norm often provides a loose approximation of true sparsity. To bridge this gap, this research introduces the $\ell_1 - \alpha \ell_2$ metric, a tighter non-convex proxy that enhances recovery performance, especially in high-coherence scenarios and diverse noise conditions.
Methodology: The $\ell_1 - \alpha \ell_2$ Dantzig Selector
The proposed model, denoted as $\ell_1 - \alpha \ell_2$-DS, is formulated as: $$\min_{x \in \mathbb{R}^n} \|x\|_1 - \alpha \|x\|_2 \quad \text{subject to} \quad \|A^\top(b - Ax)\|_\infty \leq \eta$$ where $0 < \alpha \leq 1$ is a weighting parameter. By subtracting a portion of the $\ell_2$ norm from the $\ell_1$ norm, the objective function more aggressively penalizes non-sparse solutions.
ADMM-Based Solver
To handle the non-convexity of the objective, the authors develop an algorithm using the Alternating Direction Method of Multipliers (ADMM). The constrained problem is reformulated into an unconstrained penalty version. A key feature of the implementation is a self-adaptive strategy for updating $\alpha$ iteratively, ensuring stable convergence toward high-quality local minima.
Experimental Evaluation
The model was evaluated using two types of sensing matrices: Random Gaussian matrices and Oversampled Partial DCT matrices. The latter is particularly challenging due to high column coherence.
Robustness to Diverse Noise
A significant advantage of the Dantzig selector framework is its "noise-blind" nature. Unlike methods optimized specifically for Gaussian noise, the $\ell_\infty$ constraint effectively handles diverse distributions, including impulsive noise characterized by heavy tails and frequent outliers.
Key Results
Numerical results indicate that the $\ell_1 - \alpha \ell_2$-DS consistently achieves higher Signal-to-Noise Ratios (SNR) and lower reconstruction errors than standard $\ell_1$-DS and $\ell_p$-DS ($0 < p < 1$) methods.
In tests involving oversampled DCT matrices with Gaussian noise ($\sigma = 10^{-3}$), the proposed method achieved an SNR of 41.35 dB, significantly outperforming the 29.52 dB achieved by the standard $\ell_1$ Dantzig selector. Similar improvements were observed under impulsive and uniform noise, demonstrating the model's versatility across different sensing environments.
Conclusion
The $\ell_1 - \alpha \ell_2$ Dantzig selector offers a robust and accurate alternative for sparse signal recovery. By leveraging a tighter sparsity proxy and an efficient ADMM algorithm, it overcomes the limitations of traditional convex methods, particularly in noisy and high-coherence environments. While the non-convex nature presents computational challenges, the performance gains in reconstruction accuracy make it a compelling choice for advanced signal processing applications.
Summary updated