$L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver

摘要

The special importance of $L_{1/2}$ regularization has been recognized in recent studies on sparse modeling (particularly on compressed sensing). The $L_{1/2}$ regularization, however, leads to a nonconvex, nonsmooth, and non-Lipschitz optimization problem that is difficult to solve fast and efficiently. In this paper, through developing a threshoding representation theory for $L_{1/2}$ regularization, we propose an iterative $half$ thresholding algorithm for fast solution of $L_{1/2}$ regularization, corresponding to the well-known iterative $soft$ thresholding algorithm for $L_{1}$ regularization, and the iterative $hard$ thresholding algorithm for $L_{0}$ regularization. We prove the existence of the resolvent of gradient of $Vert xVert^{1/2}_{1/2}$, calculate its analytic expression, and establish an alternative feature theorem on solutions of $L_{1/2}$ regularization, based on which a thresholding representation of solutions of $L_{1/2}$ regularization is derived and an optimal regularization parameter setting rule is formulated. The developed theory provides a successful practice of extension of the well-known Moreau's proximity forward-backward splitting theory to the $L_{1/2}$ regularization case. We verify the convergence of the iterative $half$ thresholding algorithm and provide a series of experiments to assess performance of the algorithm. The experiments show that the ${half}$ algorithm is effective, efficient, and can be accepted as a fast solver for $L_{1/2}$ regularization. With the new algorithm, we conduct a phase diagram study to further demonstrate the superiority of $L_{1/2}$ regularization over $L_{1}$ regularization.