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
DOI: https://doi.org/10.1090/mcom/3004
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?)

  • [1] İlker Bayram and Ivan W. Selesnick, A subband adaptive iterative shrinkage/thresholding algorithm, IEEE Trans. Signal Process. 58 (2010), no. 3, 1131-1143. MR 2730202 (2011g:94012), https://doi.org/10.1109/TSP.2009.2036064
  • [2] Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183-202. MR 2486527 (2010d:35390), https://doi.org/10.1137/080716542
  • [3] S. Becker, CoSaMP and OMP for sparse recovery, Matlab Central File Exchange, 08/01/11 (Updated 04/20/12).
  • [4] Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 265-274. MR 2559726 (2010i:94048), https://doi.org/10.1016/j.acha.2009.04.002
  • [5] Martin Burger, Guy Gilboa, Stanley Osher, and Jinjun Xu, Nonlinear inverse scale space methods, Commun. Math. Sci. 4 (2006), no. 1, 179-212. MR 2204083 (2006i:35177)
  • [6] Martin Burger, Michael Möller, Martin Benning, and Stanley Osher, An adaptive inverse scale space method for compressed sensing, Math. Comp. 82 (2013), no. 281, 269-299. MR 2983025, https://doi.org/10.1090/S0025-5718-2012-02599-3
  • [7] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Convergence of the linearized Bregman iteration for $ \ell _1$-norm minimization, Math. Comp. 78 (2009), no. 268, 2127-2136. MR 2521281 (2010k:65111), https://doi.org/10.1090/S0025-5718-09-02242-X
  • [8] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515-1536. MR 2501061 (2010e:65086), https://doi.org/10.1090/S0025-5718-08-02189-3
  • [9] Emmanuel J. Candes and Terence Tao, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406-5425. MR 2300700 (2008c:94009), https://doi.org/10.1109/TIT.2006.885507
  • [10] Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203-4215. MR 2243152 (2007b:94313), https://doi.org/10.1109/TIT.2005.858979
  • [11] Wei Dai and Olgica Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory 55 (2009), no. 5, 2230-2249. MR 2729876 (2011e:94057), https://doi.org/10.1109/TIT.2009.2016006
  • [12] David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. MR 2241189 (2007e:94013), https://doi.org/10.1109/TIT.2006.871582
  • [13] David L. Donoho and Michael Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $ l^1$ minimization, Proc. Natl. Acad. Sci. USA 100 (2003), no. 5, 2197-2202 (electronic). MR 1963681 (2004c:94068), https://doi.org/10.1073/pnas.0437847100
  • [14] D.L. Donoho, A. Maleki, and A. Montanari, Message passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences 106 (2009), no. 45, 18914-18919.
  • [15] E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, Tech. report, 2009, UCLA CAM Report [09-31].
  • [16] Simon Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal. 49 (2011), no. 6, 2543-2563. MR 2873246 (2012m:65095), https://doi.org/10.1137/100806278
  • [17] Simon Foucart, Stability and robustness of weak orthogonal matching pursuits, Recent Advances in Harmonic Analysis and Applications, Springer Proc. Math. Stat., vol. 25, Springer, New York, 2013, pp. 395-405. MR 3066900, https://doi.org/10.1007/978-1-4614-4565-4_30
  • [18] Elaine T. Hale, Wotao Yin, and Yin Zhang, Fixed-point continuation for $ l_1$-minimization: methodology and convergence, SIAM J. Optim. 19 (2008), no. 3, 1107-1130. MR 2460734 (2009j:90070), https://doi.org/10.1137/070698920
  • [19] P. Jain, A. Tewari, and I.S. Dhillon, Orthogonal matching pursuit with replacement, Tech. Report arXiv:1106.2774, 2011.
  • [20] A. Maleki, Coherence analysis of iterative thresholding algorithms, Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, IEEE Press, 2009, pp. 236-243.
  • [21] A. Maleki and D.L. Donoho, Optimally tuned iterative reconstruction algorithms for compressed sensing, IEEE J. of Selected Topics in Sig. Processing 4 (2010), no. 2, 330-341.
  • [22] S.G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. on Sig. Processing 12 (1993), 3397-3415.
  • [23] Michael Moeller and Martin Burger, Multiscale methods for polyhedral regularizations, SIAM J. Optim. 23 (2013), no. 3, 1424-1456. MR 3073657, https://doi.org/10.1137/110858136
  • [24] D. Needell and J. A. Tropp, CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (2009), no. 3, 301-321. MR 2502366 (2010c:94018), https://doi.org/10.1016/j.acha.2008.07.002
  • [25] Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460-489 (electronic). MR 2162864 (2006c:49051), https://doi.org/10.1137/040605412
  • [26] Stanley Osher, Yu Mao, Bin Dong, and Wotao Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), no. 1, 93-111. MR 2655902 (2011c:90098)
  • [27] F. Parvaresh, H. Vikalo, S. Misra, and B. Hassibi, Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays, IEEE J. of Selected Topics in Signal Processing 2 (2008), 275-285.
  • [28] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, 1993, pp. 40-44.
  • [29] Holger Rauhut, Compressive sensing and structured random matrices, Theoretical foundations and numerical methods for sparse recovery, Radon Ser. Comput. Appl. Math., vol. 9, Walter de Gruyter, Berlin, 2010, pp. 1-92. MR 2731597 (2012h:94098), https://doi.org/10.1515/9783110226157.1
  • [30] Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231-2242. MR 2097044 (2005e:94036), https://doi.org/10.1109/TIT.2004.834793
  • [31] Joel A. Tropp and Anna C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory 53 (2007), no. 12, 4655-4666. MR 2446929 (2009h:94042), https://doi.org/10.1109/TIT.2007.909108
  • [32] Joel A. Tropp, Algorithms for simultaneous sparse approximation: part II: Convex relaxation, Signal Process. 86 (2006), no. 3, 589-602.
  • [33] Yi Yang, Michael Möller, and Stanley Osher, A dual split Bregman method for fast $ \ell ^1$ minimization, Math. Comp. 82 (2013), no. 284, 2061-2085. MR 3073192, https://doi.org/10.1090/S0025-5718-2013-02700-7
  • [34] Zai Yang, Cishen Zhang, Jun Deng, and Wenmiao Lu, Orthonormal expansion $ \ell _1$-minimization algorithms for compressed sensing, IEEE Trans. Signal Process. 59 (2011), no. 12, 6285-6290. MR 2907924, https://doi.org/10.1109/TSP.2011.2168216
  • [35] Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $ l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143-168. MR 2475828 (2010f:90170), https://doi.org/10.1137/070703983
  • [36] Xiaoqun Zhang, Martin Burger, and Stanley Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput. 46 (2011), no. 1, 20-46. MR 2753250 (2012f:90120), https://doi.org/10.1007/s10915-010-9408-8

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
Email: m.moeller@gmx.net

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
Email: xqzhang@sjtu.edu.cn

DOI: https://doi.org/10.1090/mcom/3004
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

American Mathematical Society