Volume 35, Issue 4
Iterative $ℓ_1$ Minimization for Non-Convex Compressed Sensing

Penghang YinJack Xin

J. Comp. Math., 35 (2017), pp. 439-451.

Published online: 2017-08

[An open-access article; the PDF is free to any online user.]

Preview Full PDF 585 3289
Export citation
  • 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.

  • Keywords

Compressed sensing, Non-convexity, Difference of convex functions algorithm, Iterative $ℓ_1$ minimization.

  • AMS Subject Headings

90C26, 65K10, 49M29

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

yph@ucla.edu (Penghang Yin)

jxin@math.uci.edu (Jack Xin)

  • BibTex
  • RIS
  • TXT
@Article{JCM-35-439, author = {Yin , Penghang and Xin , Jack}, title = {Iterative $ℓ_1$ Minimization for Non-Convex Compressed Sensing}, journal = {Journal of Computational Mathematics}, year = {2017}, volume = {35}, number = {4}, pages = {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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1610-m2016-0620}, url = {http://global-sci.org/intro/article_detail/jcm/10025.html} }
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 -

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.

Penghang Yin & Jack Xin. (2019). Iterative $ℓ_1$ Minimization for Non-Convex Compressed Sensing. Journal of Computational Mathematics. 35 (4). 439-451. doi:10.4208/jcm.1610-m2016-0620
Copy to clipboard
The citation has been copied to your clipboard