Iterative _1 minimization for non-convex compressed sensing

DOI10.4208/JCM.1610-M2016-0620MaRDI QIDQ4688141zbMATH OpenOpenAlexFDO

Authors Penghang Yin, Jack Xin

Publication date 22 October 2018

Published in Journal of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.07924

zbMATH Keywords

compressed sensingdifference of convex functions algorithmiterative \({\ell_1}\) minimizationnon-convexity

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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 $el{l}_1$ minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit ($el{l}_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 $el{l}_1$ (IL${}_1$) algorithm lead by a wide margin the state-of-the-art algorithms on $el{l}_{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), IL${}_1$ algorithm easily recovers the phantom image with just 7 line projections.

Recommendations

• Minimization of \(\ell_{1-2}\) for compressed sensing
• Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
• Computational Aspects of Constrained L 1-L 2 Minimization for Compressive Sensing
• An l₁-l_p DC regularization method for compressed sensing
• Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing

Cited in

(16)

• Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
• Linear feature transform and enhancement of classification on deep neural network
• A non-convex regularization approach for compressive sensing
• A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations
• Coordinate descent optimization for \(l^{1}\) minimization with application to compressed sensing; a greedy algorithm
• Linearized Bregman iterations for compressed sensing
• An l₁-l_p DC regularization method for compressed sensing
• Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
• Orthonormal Expansion $\ell_{1}$-Minimization Algorithms for Compressed Sensing
• A null-space-based weightedl₁minimization approach to compressed sensing
• Minimization of \(\ell_{1-2}\) for compressed sensing
• Computational Aspects of Constrained L 1-L 2 Minimization for Compressive Sensing
• Doubly iteratively reweighted algorithm for constrained compressed sensing models
• Alternating direction method of multipliers with difference of convex functions
• Avoiding strict saddle points of nonconvex regularized problems
• Matrix-free interior point method for compressed sensing problems

This page was built for publication: Iterative \({\ell_1}\) minimization for non-convex compressed sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4688141)