A fast algorithm for nonconvex approaches to sparse recovery problems

被引:31
作者
Montefusco, Laura B. [1 ]
Lazzaro, Damiana [1 ]
Papi, Serena [2 ]
机构
[1] Univ Bologna, Dept Math, I-40123 Bologna, Italy
[2] Univ Bologna, CIRI ICT, I-47521 Cesena, FC, Italy
关键词
Compressed sensing; Nonconvex minimization; Splitting methods; Penalization method; Reweighted methods; NONCONCAVE PENALIZED LIKELIHOOD; REWEIGHTED LEAST-SQUARES; SIGNAL RECOVERY; RECONSTRUCTION; MINIMIZATION; CONVERGENCE;
D O I
10.1016/j.sigpro.2013.02.018
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
This paper addresses the problem of sparse signal recovery from a lower number of measurements than those requested by the classical compressed sensing theory. This problem is formalized as a constrained minimization problem, where the objective function is nonconvex and singular at the origin. Several algorithms have been recently proposed, which rely on iterative reweighting schemes, that produce better estimates at each new minimization step. Two such methods are iterative reweighted l(2) and l(1) minimization that have been shown to be effective and general, but very computationally demanding. The main contribution of this paper is the proposal of the algorithm WNFCS, where the reweighted schemes represent the core of a penalized approach to the solution of the constrained nonconvex minimization problem. The algorithm is fast, and succeeds in exactly recovering a sparse signal from a smaller number of measurements than the l(1) minimization and in a shorter time. WNFCS is very general, since it represents an algorithmic framework that can easily be adapted to different reweighting strategies and nonconvex objective functions. Several numerical experiments and comparisons with some of the most recent nonconvex minimization algorithms confirm the capabilities of the proposed algorithm. (c) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:2636 / 2647
页数:12
相关论文
共 50 条
[21]   NESTA: A Fast and Accurate First-Order Method for Sparse Recovery [J].
Becker, Stephen ;
Bobin, Jerome ;
Candes, Emmanuel J. .
SIAM JOURNAL ON IMAGING SCIENCES, 2011, 4 (01) :1-39
[22]   A NONCONVEX ADMM ALGORITHM FOR GROUP SPARSITY WITH SPARSE GROUPS [J].
Chartrand, Rick ;
Wohlberg, Brendt .
2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, :6009-6013
[23]   Relax-and-split method for nonconvex inverse problems [J].
Zheng, Peng ;
Aravkin, Aleksandr .
INVERSE PROBLEMS, 2020, 36 (09)
[24]   Trust-Region Methods for Nonconvex Sparse Recovery Optimization [J].
Adhikari, Lasith ;
Marcia, Roummel F. ;
Erway, Jennifer B. ;
Plemmons, Robert J. .
PROCEEDINGS OF 2016 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2016), 2016, :275-279
[25]   Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere [J].
Chen, Xiaojun ;
Womersley, Robert S. .
SIAM JOURNAL ON IMAGING SCIENCES, 2018, 11 (02) :1390-1415
[26]   Nonconvex Regularization-Based Sparse Recovery and Demixing With Application to Color Image Inpainting [J].
Wen, Fei ;
Adhikari, Lasith ;
Pei, Ling ;
Marcia, Roummel F. ;
Liu, Peilin ;
Qiu, Robert C. .
IEEE ACCESS, 2017, 5 :11513-11527
[27]   FAST AND ROBUST EM-BASED IRLS ALGORITHM FOR SPARSE SIGNAL RECOVERY FROM NOISY MEASUREMENTS [J].
Ravazzi, C. ;
Magli, E. .
2015 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING (ICASSP), 2015, :3841-3845
[28]   Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery [J].
Zhang, Yanfeng ;
Huang, Yunbao ;
Li, Haiyan ;
Li, Pu ;
Fan, Xi'an .
ALGORITHMS, 2019, 12 (02)
[29]   Fast thresholding algorithms with feedbacks for sparse signal recovery [J].
Li, Shidong ;
Liu, Yulong ;
Mi, Tiebin .
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2014, 37 (01) :69-88
[30]   A Randomized Algorithm for Sparse Recovery [J].
Yu, Huiyuan ;
Cheng, Maggie ;
Lu, Yingdong .
2020 25TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION (ICPR), 2021, :8312-8319