A non-convex piecewise quadratic approximation of $$\ell _{0}$$ ℓ 0 regularization: theory and accelerated algorithm

Qian Li (), Wei Zhang (), Yanqin Bai () and Guoqiang Wang ()
Additional contact information
Qian Li: Shanghai University of Engineering Science
Wei Zhang: South China University of Technology
Yanqin Bai: Shanghai University
Guoqiang Wang: Shanghai University of Engineering Science

Journal of Global Optimization, 2023, vol. 86, issue 2, No 3, 323-353

Abstract: Abstract Non-convex regularization has been recognized as an especially important approach in recent studies to promote sparsity. In this paper, we study the non-convex piecewise quadratic approximation (PQA) regularization for sparse solutions of the linear inverse problem. It is shown that exact recovery of sparse signals and stable recovery of compressible signals are possible through local optimum of this regularization. After developing a thresholding representation theory for PQA regularization, we propose an iterative PQA thresholding algorithm (PQA algorithm) to solve this problem. The PQA algorithm converges to a local minimizer of the regularization, with an eventually linear convergence rate. Furthermore, we adopt the idea of accelerated gradient method to design the accelerated iterative PQA thresholding algorithm (APQA algorithm), which is also linearly convergent, but with a faster convergence rate. Finally, we carry out a series of numerical experiments to assess the performance of both algorithms for PQA regularization. The results show that PQA regularization outperforms $$\ell _1$$ ℓ 1 and $$\ell _{1/2}$$ ℓ 1 / 2 regularizations in terms of accuracy and sparsity, while the APQA algorithm is demonstrated to be significantly better than the PQA algorithm.

Keywords: Iterative thresholding algorithm; Exact recovery; Sparsity optimization; Non-convex approximation; Accelerated gradient algorithm; 90C06; 90C26; 65K05 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01257-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:86:y:2023:i:2:d:10.1007_s10898-022-01257-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01257-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().