A New Algorithm For Fast Solving L_1/2 Regularization Problem

Xu Zongben proposed L1/2regularization, which can be taken as a representative of Lq (0<q≤1) regularization in2008. It has been shown in [18,20,30] that L1/2regularization can yield sparser solutions than L1regularization, thus, it provides a potentially powerful new ap-proach for sparsity problem. However, L1/2regularization problem as a nonconvex, nonsmooth, and non-Lipschitz optimization problem, is difficult to solve fast and efficiently. Xu Zongben proposed a fast algorithm for solving L1/2regularization problem-the iterative half threshold-ing algorithm in2012, corresponding to the well-known iterative hard thresholding algorithm for L0regularization problem,and the iterative soft thresholding algorithm for L1regularization problem.Amir Beck improved soft threshold iterative algorithm, and proposed a fast soft threshold-ing algorithm. The main idea of the algorithm is applied accelerate proximal gradient method (APG) and soft thresholding operator to solve L1regularization problem. We propose a new al-gorithm for L1/2regularization problem based on APG method and half thresholding operator, we provide a series of experiments to assess performance of the algorithm, such as, Compressed Sensing,Image De-noising and so on. The experiments show that:(1)our algorithm is more ef-fective and efficient than the iterative half thresholding algorithm, and can be taken as another fast solver for L1/2regularization problem;(2)our algorithm is simple and suitable for large-scale problems;(3)our algorithm is robust to overestimation of sparsity value, when the number of measurements is large;(4)The experiments verify the superiority of L1/2regularization over L1regularization.