TY - JOUR
T1 - Iterative $ℓ_1$ Minimization for Non-Convex Compressed Sensing
AU - Yin , Penghang
AU - Xin , Jack
JO - Journal of Computational Mathematics
VL - 4
SP - 439
EP - 451
PY - 2017
DA - 2017/08
SN - 35
DO - http://doi.org/10.4208/jcm.1610-m2016-0620
UR - https://global-sci.org/intro/article_detail/jcm/10025.html
KW - Compressed sensing, Non-convexity, Difference of convex functions algorithm, Iterative $ℓ_1$ minimization.
AB - <p style="text-align: justify;">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.</p>