The Dantzig selector: Recovery of Signal via $\ell_1-\alpha \ell_2$ Minimization

Huanmin Ge, Peng Li

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.

Probability Density Function (PDF) of the $\alpha$-stable distribution used to model impulsive noise.

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.

Performance comparison across different noise types and sensing matrices.

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

Abstract

In the paper, we proposed the Dantzig selector based on the $\ell_{1}-\alpha \ell_{2}$~$(0 0$ means the columns of ${\bf A}$ has very weakly correlated with the error vector ${\bf e}={\bf A}{\bf x}-{\bf b}$. First, recovery guarantees based on the restricted isometry property (RIP) are established for signals. Next, we propose the effective algorithm to solve the proposed Dantzig selector. Last, we illustrate the proposed model and algorithm by extensive numerical experiments for the recovery of signals in the cases of Gaussian, impulsive and uniform noise. And the performance of the proposed Dantzig selector is better than that of the existing methods.
BibTeX
@misc{ge2021dantzig,
  author = {Huanmin Ge and Peng Li},
  title = {{The Dantzig selector: Recovery of Signal via $\textbackslash\{\}ell\_1-\textbackslash\{\}alpha \textbackslash\{\}ell\_2$ Minimization}},
  year = {2021},
  eprint = {2105.14229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14229},
}
Figure