Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm

DOI10.1109/TSP.2016.2595499MaRDI QIDQ4620964zbMATH OpenOpenAlexFDO

Authors Jinshan Zeng, Shaobo Lin, Zongben Xu

Publication date 8 February 2019

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

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In recent studies on sparse modeling, non-convex penalties have received considerable attentions due to their superiorities on sparsity-inducing over the convex counterparts. Compared with the convex optimization approaches, however, the non-convex approaches have more challenging convergence analysis. In this paper, we study the convergence of a non-convex iterative thresholding algorithm for solving sparse recovery problems with a certain class of non-convex penalties, whose corresponding thresholding functions are discontinuous with jump discontinuities. Therefore, we call the algorithm the iterative jumping thresholding (IJT) algorithm. The finite support and sign convergence of IJT algorithm is firstly verified via taking advantage of such jump discontinuity. Together with the assumption of the introduced restricted Kurdyka-{L}ojasiewicz (rKL) property, then the strong convergence of IJT algorithm can be proved.Furthermore, we can show that IJT algorithm converges to a local minimizer at an asymptotically linear rate under some additional conditions. Moreover, we derive a posteriori computable error estimate, which can be used to design practical terminal rules for the algorithm. It should be pointed out that the $l_q$ quasi-norm ($0<q<1$) is an important subclass of the class of non-convex penalties studied in this paper. In particular, when applied to the $l_q$ regularization, IJT algorithm can converge to a local minimizer with an asymptotically linear rate under certain concentration conditions. We provide also a set of simulations to support the correctness of theoretical assertions and compare the time efficiency of IJT algorithm for the $l_q$ regularization ($q=1/2,2/3$) with other known typical algorithms like the iterative reweighted least squares (IRLS) algorithm and the iterative reweighted $l_1$ minimization (IRL1) algorithm.

Cited in

(12)

• Smoothed \(L_{1/2}\) regularizer learning for split-complex valued neuro-fuzzy algorithm for TSK system and its convergence results
• A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
• Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
• Relating _p regularization and reweighted _1 regularization
• Analysis of compressed distributed adaptive filters
• Sparse signal recovery by accelerated \(\ell_q\) \((0<q<1)\) thresholding algorithm
• <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm
• Computational approaches to non-convex, sparsity-inducing multi-penalty regularization
• An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis
• A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
• A non-convex piecewise quadratic approximation of _0 regularization: theory and accelerated algorithm
• Avoiding strict saddle points of nonconvex regularized problems

This page was built for publication: Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm

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