Linearized alternating directions method for ℓ₁-norm inequality constrained ℓ₁-norm minimization

The ℓ₁-regularization is popular in compressive sensing due to its ability to promote sparsity property. In the past few years, intensive research activities have been attracted to the algorithms for ℓ₁-regularized least squares or its multifarious variations. In this study, we consider the ℓ₁-norm minimization problems simultaneously with ℓ₁-norm inequality constraints. The formulation of this problem is preferable when the measurement of a large and sparse signal is corrupted by an impulsive noise, in the mean time the noise level is given. This study proposes and investigates an inexact alternating direction method. At each iteration, as the closed-form solution of the resulting subproblem is not clear, we apply a linearized technique such that the closed-form solutions of the linearized subproblem can be easily derived. Global convergence of the proposed method is established under some appropriate assumptions. Numerical results, including comparisons with another algorithm are reported which demonstrate the superiority of the proposed algorithm. Finally, we extend the algorithm to solve ^ℓ2-norm constrained ℓ₁-norm minimization problem, and show that the linearized technique can be avoided.