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

The ℓ1ℓ1-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 ℓ1ℓ1-regularized least squares or its multifarious variations. In this study, we consider the ℓ1ℓ1-norm minimization problems simultaneously with ℓ1ℓ1-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ℓ2-norm constrained ℓ1ℓ1-norm minimization problem, and show that the linearized technique can be avoided.