$L_{1/2}$ Regularization: Convergence of Iterative Half Thresholding Algorithm

Abstract

In recent studies on sparse modeling, the nonconvex regularization approaches (particularly, $L_q$ regularization with $q\in (0,1)$) have been demonstrated to possess capability of gaining much benefit in sparsity-inducing and efficiency. As compared with the convex regularization approaches (say, $L_1$ regularization), however, the convergence issue of the corresponding algorithms are more difficult to tackle. In this paper, we deal with this difficult issue for a specific but typical nonconvex regularization scheme, the $L_{1/2}$ regularization, which has been successfully used to many applications. More specifically, we study the convergence of the iterative \textit{half} thresholding algorithm (the \textit{half} algorithm for short), one of the most efficient and important algorithms for solution to the $L_{1/2}$ regularization. As the main result, we show that under certain conditions, the \textit{half} algorithm converges to a local minimizer of the $L_{1/2}$ regularization, with an eventually linear convergence rate. The established result provides a theoretical guarantee for a wide range of applications of the \textit{half} algorithm. We provide also a set of simulations to support the correctness of theoretical assertions and compare the time efficiency of the \textit{half} algorithm with other known typical algorithms for $L_{1/2}$ regularization like the iteratively reweighted least squares (IRLS) algorithm and the iteratively reweighted $l_1$ minimization (IRL1) algorithm.

12 pages, 5 figures

References in corpus (4)

• Structured Compressed Sensing: From Theory to Applications
• Certifying the restricted isometry property is hard
• Compressed Sensing and Affine Rank Minimization under Restricted Isometry
• Hidden cliques and the certification of the restricted isometry property

Cited by in corpus (19)

• A survey of sparse representation: algorithms and applications
• Global convergence of splitting methods for nonconvex composite optimization
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Learning optimal nonlinearities for iterative thresholding algorithms
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Minimization of Transformed $L_1$ Penalty: Theory, Difference of Convex Function Algorithm, and Robust Application in Compressed Sensing
• Total Variation with Overlapping Group Sparsity and Lp Quasinorm for Infrared Image Deblurring under Salt-and-Pepper Noise
• Minimization of Transformed $L_1$ Penalty: Closed Form Representation and Iterative Thresholding Algorithms
• Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm
• Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
• Matrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
• A Cyclic Coordinate Descent Algorithm for lq Regularization
• A Gauss-Seidel Iterative Thresholding Algorithm for lq Regularized Least Squares Regression
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• Hierarchical Group Sparse Regularization for Deep Convolutional Neural Networks
• Greedy Criterion in Orthogonal Greedy Learning