Fast sparse reconstruction: Greedy inverse scale space flows

Moeller, Michael; Zhang, Xiaoqun

doi:10.1090/mcom/3004

Fast sparse reconstruction: Greedy inverse scale space flows
HTML articles powered by AMS MathViewer

by Michael Moeller and Xiaoqun Zhang;

Math. Comp. 85 (2016), 179-208

DOI: https://doi.org/10.1090/mcom/3004

Published electronically: July 29, 2015

PDF | Request permission

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

İ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, DOI 10.1109/TSP.2009.2036064
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, DOI 10.1137/080716542
S. Becker, CoSaMP and OMP for sparse recovery, Matlab Central File Exchange, 08/01/11 (Updated 04/20/12).
Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 265–274. MR 2559726, DOI 10.1016/j.acha.2009.04.002
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
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, DOI 10.1090/S0025-5718-2012-02599-3
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, DOI 10.1090/S0025-5718-09-02242-X
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515–1536. MR 2501061, DOI 10.1090/S0025-5718-08-02189-3
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, DOI 10.1109/TIT.2006.885507
Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
Wei Dai and Olgica Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory 55 (2009), no. 5, 2230–2249. MR 2729876, DOI 10.1109/TIT.2009.2016006
David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
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. MR 1963681, DOI 10.1073/pnas.0437847100
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.
E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, Tech. report, 2009, UCLA CAM Report [09-31].
Simon Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal. 49 (2011), no. 6, 2543–2563. MR 2873246, DOI 10.1137/100806278
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, DOI 10.1007/978-1-4614-4565-4_{3}0
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, DOI 10.1137/070698920
P. Jain, A. Tewari, and I.S. Dhillon, Orthogonal matching pursuit with replacement, Tech. Report arXiv:1106.2774, 2011.
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.
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.
S.G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. on Sig. Processing 12 (1993), 3397–3415.
Michael Moeller and Martin Burger, Multiscale methods for polyhedral regularizations, SIAM J. Optim. 23 (2013), no. 3, 1424–1456. MR 3073657, DOI 10.1137/110858136
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, DOI 10.1016/j.acha.2008.07.002
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. MR 2162864, DOI 10.1137/040605412
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
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.
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.
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, DOI 10.1515/9783110226157.1
Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231–2242. MR 2097044, DOI 10.1109/TIT.2004.834793
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, DOI 10.1109/TIT.2007.909108
Joel A. Tropp, Algorithms for simultaneous sparse approximation: part II: Convex relaxation, Signal Process. 86 (2006), no. 3, 589–602.
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, DOI 10.1090/S0025-5718-2013-02700-7
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, DOI 10.1109/TSP.2011.2168216
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, DOI 10.1137/070703983
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, DOI 10.1007/s10915-010-9408-8