Two-level ℓ1 minimization for compressed sensing

Compressed sensing using ℓ1 minimization has been widely and successfully applied. To further enhance the sparsity, a non-convex and piecewise linear penalty is proposed. This penalty gives two different weights according to the order of the absolute value and hence is called the two-level ℓ1-norm. The two-level ℓ1-norm can be minimized by an iteratively reweighted ℓ1 method. Compared with some existing non-convex methods, the two-level ℓ1 minimization has similar sparsity and enjoys good convergence behavior. More importantly, the related soft thresholding algorithm has been established. The shrinkage operator for the two-level ℓ1-norm is not non-expansive and its convergence is proved by showing the monotone of the objective value in the iterations. In numerical experiments, the proposed algorithms achieve good sparse signal estimation performance, which makes the two-level ℓ1 minimization a promising technique for compressed sensing.