Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast sparse reconstruction: Greedy inverse scale space flows

Authors: Michael Moeller and Xiaoqun Zhang
Journal: Math. Comp. 85 (2016), 179-208
MSC (2010): Primary 65K10, 90C59, 90C26; Secondary 92C55
Published electronically: July 29, 2015
MathSciNet review: 3404447
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we analyze the connection between the recently proposed adaptive inverse scale space methods for basis pursuit and the well-known orthogonal matching pursuit method for the recovery of sparse solutions to underdetermined linear systems. Furthermore, we propose a new greedy sparse recovery method, which approximates $\ell ^1$ minimization more closely. A variant of our new approach can increase the support of the current iterate by many indices at once, resulting in an extremely efficient algorithm. Our new method has the advantage that there is a simple criterion to determine a posteriori if an $\ell ^1$ minimizer was found. Numerical comparisons with orthogonal matching pursuit, weak orthogonal matching pursuit, hard thresholding pursuit and compressive sampling matching pursuit underline that our methods indeed inherit some advantageous properties from the inverse scale space flow.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65K10, 90C59, 90C26, 92C55

Retrieve articles in all journals with MSC (2010): 65K10, 90C59, 90C26, 92C55

Additional Information

Michael Moeller
Affiliation: Institue for Computational and Applied Mathematics, University of Münster, Germany
Address at time of publication: Department of Mathematics, Technische Universität München, Boltzmannstrasse 3, 85748 Garching, Germany
MR Author ID: 974311

Xiaoqun Zhang
Affiliation: Department of Mathematics, MOE-LSC and Institute of Natural Sciences, Shanghai Jiao Tong University, No. 800, Dongchuan Road, Shanghai 200240, People’s Republic of China

Received by editor(s): January 30, 2013
Received by editor(s) in revised form: January 26, 2014
Published electronically: July 29, 2015
Additional Notes: This work was supported by the DFG grant “Sparsity constrained inversion with Tomographic Applications”
The second author was additionally supported by the National Science Foundation of China (grant numbers NSFC91330102, NSFC11101277 and NSFC11161130004) and by the Shanghai Pujiang Talent program (grant number 11PJ1405900)
Article copyright: © Copyright 2015 American Mathematical Society