<formula formulatype="inline"><tex Notation="TeX">L_{1/2}</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm

DOI10.1109/TSP.2014.2309076MaRDI QIDQ4579171zbMATH OpenOpenAlexFDO

Authors Jinshan Zeng, Yao Wang, Shaobo Lin, Zongben Xu

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.0156

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In recent studies on sparse modeling, the nonconvex regularization approaches (particularly, $L_q$ regularization with $qin(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 extit{half} thresholding algorithm (the extit{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 extit{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 extit{half} algorithm. We provide also a set of simulations to support the correctness of theoretical assertions and compare the time efficiency of the extit{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.

Recommendations

• A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem
• Iterative thresholding algorithm based on non-convex method for modified l_p-norm regularization minimization
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm
• On the Convergence of the Iterative Shrinkage/Thresholding Algorithm With a Weakly Convex Penalty
• Convergence of iterative hard-thresholding algorithm with continuation
• Linear convergence of iterative soft-thresholding
• A new linear convergence result for the iterative soft thresholding algorithm
• Accelerated iterative hard thresholding algorithm for \(l_0\) regularized regression problem
• Minimization of transformed \(l_1\) penalty: closed form representation and iterative thresholding algorithms

Cited in

(36)

• MOEA/D with chain-based random local search for sparse optimization
• Global optimality condition and fixed point continuation algorithm for non-Lipschitz _p regularized matrix minimization
• The sparsity of underdetermined linear system via \(l_p\) minimization for \(0 < p < 1\)
• A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
• Sparse principal component analysis via fractional function regularity
• Smoothing inertial projection neural network for minimization \(L_{p-q}\) in sparse signal reconstruction
• Image restoration via the adaptive \(TV^p\) regularization
• Adaptive decomposition-based evolutionary approach for multiobjective sparse reconstruction
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• Remote sensing images destriping using unidirectional hybrid total variation and nonconvex low-rank regularization
• Conic formulation of QPCCs applied to truly sparse QPs
• A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• The non-convex sparse problem with nonnegative constraint for signal reconstruction
• Global convergence of splitting methods for nonconvex composite optimization
• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• A new sufficient condition for sparse vector recovery via _1- _2 local minimization
• Non-convex optimization via strongly convex majorization-minimization
• GAITA: a Gauss-Seidel iterative thresholding algorithm for _q regularized least squares regression
• An efficient proximal block coordinate homotopy method for large-scale sparse least squares problems
• Convergence of iterative hard-thresholding algorithm with continuation
• Minimization of \(\ell_{1-2}\) for compressed sensing
• Doubly majorized algorithm for sparsity-inducing optimization problems with regularizer-compatible constraints
• A wonderful triangle in compressed sensing
• A non-convex piecewise quadratic approximation of _0 regularization: theory and accelerated algorithm
• Identifying stochastic governing equations from data of the most probable transition trajectories
• Group sparse structural smoothing recovery: model, statistical properties and algorithm
• An efficient regularized PR splitting type algorithm for two-block nonconvex linear constrained programs in \(\ell_{1 / 2}\) regularized compressed sensing problems
• Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
• Convergence analysis of Bregman ADMM for three-block nonconvex indivisible optimization problems with linearization technique
• A distributed Douglas-Rachford splitting method for solving linear constrained multi-block weakly convex problems
• Accelerated preconditioning half thresholding algorithms for \(L_{1/2}\) regularization
• A projection-based neurodynamic system method with convergence guarantees for \(L_q\)-regularized \((0 < q < 1)\) sparse recovery problem
• A compression recovery method based on non-convex regularization and log-TV regularization

This page was built for publication: <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579171)