Iterative ℓ1 Minimization for Non-Convex Compressed Sensing
Year: 2017
Author: Penghang Yin, Jack Xin
Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 439–451
Abstract
An algorithmic framework, based on the difference of convex functions algorithm (DCA), is proposed for minimizing a class of concave sparse metrics for compressed sensing problems. The resulting algorithm iterates a sequence of ℓ1 minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit (ℓ1 minimization) and inherits robustness from it. Numerical examples on success rates of sparse solution recovery illustrate further that, unlike most existing non-convex compressed sensing solvers in the literature, our method always out-performs basis pursuit, no matter how ill-conditioned the measurement matrix is. Moreover, the iterative ℓ1 (IL1) algorithm lead by a wide margin the state-of-the-art algorithms on ℓ1/2 and logarithimic minimizations in the strongly coherent (highly ill-conditioned) regime, despite the same objective functions. Last but not least, in the application of magnetic resonance imaging (MRI), IL1 algorithm easily recovers the phantom image with just 7 line projections.
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1610-m2016-0620
Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 439–451
Published online: 2017-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 13
Keywords: Compressed sensing Non-convexity Difference of convex functions algorithm Iterative ℓ1 minimization.
Author Details
Penghang Yin Email
Jack Xin Email
-
A dictionary‐based graph‐cut algorithm for MRI reconstruction
Xu, Jiexun | Pannetier, Nicolas | Raj, AshishNMR in Biomedicine, Vol. 33 (2020), Iss. 12
https://doi.org/10.1002/nbm.4344 [Citations: 0] -
Minimization of transformed L1 L 1 penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
Zhang, Shuai | Xin, JackMathematical Programming, Vol. 169 (2018), Iss. 1 P.307
https://doi.org/10.1007/s10107-018-1236-x [Citations: 85] -
Sparse optimization problem with s-difference regularization
Sun, Yuli | Tan, Xiang | Li, Xiao | Lei, Lin | Kuang, GangyaoSignal Processing, Vol. 168 (2020), Iss. P.107369
https://doi.org/10.1016/j.sigpro.2019.107369 [Citations: 9] -
Linear Feature Transform and Enhancement of Classification on Deep Neural Network
Yin, Penghang | Xin, Jack | Qi, YingyongJournal of Scientific Computing, Vol. 76 (2018), Iss. 3 P.1396
https://doi.org/10.1007/s10915-018-0666-1 [Citations: 1]