Volume 35, Issue 4
Iterative l1 Minimization for Non-Convex Compressed Sensing

Penghang Yin & Jack 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 14 605
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 l1 minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit (l1 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 l1 (IL1) algorithm lead by a wide margin the state-of-the-art algorithms on l1 ⁄ 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 l_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)

  • References
  • Hide All
    View All

@Article{JCM-35-439, author = {Yin , Penghang and Xin , Jack }, title = {Iterative l1 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 l1 minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit (l1 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 l1 (IL1) algorithm lead by a wide margin the state-of-the-art algorithms on l1 ⁄ 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} }
Copy to clipboard
The citation has been copied to your clipboard