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

摘要

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