An adaptive inverse scale space method for compressed sensing
HTML articles powered by AMS MathViewer
- by Martin Burger, Michael Möller, Martin Benning and Stanley Osher PDF
- Math. Comp. 82 (2013), 269-299 Request permission
Abstract:
In this paper we introduce a novel adaptive approach for solving $\ell ^1$-minimization problems as frequently arising in compressed sensing, which is based on the recently introduced inverse scale space method. The scheme allows to efficiently compute minimizers by solving a sequence of low-dimensional nonnegative least-squares problems.
We provide a detailed convergence analysis in a general setup as well as refined results under special conditions. In addition, we discuss experimental observations in several numerical examples.
References
- M. Benning, T. Kösters, F. Wübbeling, K. Schäfers, and M. Burger, A nonlinear variational method for improved quantification of myocardial blood flow using dynamic H215O PET, IEEE Nuclear Science Symposium Conference Record, 2008, pp. 4472–4477.
- 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
- M. Burger, A note on sparse reconstruction methods, J. Phys. Conference Series, no. 012002, 2008.
- M. Burger, K. Frick, S. Osher, and O. Scherzer, Inverse total variation flow, Multiscale Model. Simul. 6 (2007), no. 2, 365–395. MR 2338487, DOI 10.1137/060660564
- 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
- M. Burger and S. Osher, A guide to TV zoo, preprint.
- M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), no. 2-3, 109–135. MR 2354192, DOI 10.1007/s00607-007-0245-z
- 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, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
- 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
- Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27–75. MR 1803124, DOI 10.1090/S0025-5718-00-01252-7
- A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203–245. MR 1907380, DOI 10.1007/s102080010027
- Stephan Dahlke, Wolfgang Dahmen, and Karsten Urban, Adaptive wavelet methods for saddle point problems—optimal convergence rates, SIAM J. Numer. Anal. 40 (2002), no. 4, 1230–1262. MR 1951893, DOI 10.1137/S003614290139233X
- Ingrid Daubechies, Michel Defrise, and Christine De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413–1457. MR 2077704, DOI 10.1002/cpa.20042
- 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, Y. Tsaig, I. Drori, and J. L. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit (stomp), Tech. report, Stanford Univ., 2006, Stat. Dept. Tech. Rep. 2006-02.
- Ivar Ekeland and Roger Témam, Convex analysis and variational problems, Corrected reprint of the 1976 English edition, Classics in Applied Mathematics, vol. 28, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Translated from the French. MR 1727362, DOI 10.1137/1.9781611971088
- S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing 12 (1993), 3397–3415.
- Yves Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, 2001. The fifteenth Dean Jacqueline B. Lewis memorial lectures. MR 1852741, DOI 10.1090/ulect/022
- 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
- D. Needell, J. A. Tropp, and R. Vershynin, Greedy signal recovery review, Proc. 42nd Asilomar Conf. Signals, Systems and Computers, 2008.
- D. Needell and R. Vershynin, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Topics Signal Process 4 (2009), 310–316.
- 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
- 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.
- A. J. Reader, J. C. Matthews, F. C. Sureau, C. Comtat, R. Trébossen, and I. Buvat, Fully 4D image reconstruction by estimation of an input function and spectral coefficients, IEEE Nuclear Science Symposium Conference Record, 2007, pp. 3260–3267.
- Joel A. Tropp, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), no. 3, 1030–1051. MR 2238069, DOI 10.1109/TIT.2005.864420
- 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
- Yilun Wang and Wotao Yin, Sparse signal reconstruction via iterative support detection, SIAM J. Imaging Sci. 3 (2010), no. 3, 462–491. MR 2679436, DOI 10.1137/090772447
- Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
- 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
Additional Information
- Martin Burger
- Affiliation: Westfälische Wilhelms-Universität Münster, Institut für Numerische und Angewandte Mathematik, Einsteinstr. 62, D 48149 Münster, Germany
- Email: martin.burger@wwu.de
- Michael Möller
- Affiliation: Westfälische Wilhelms-Universität Münster, Institut für Numerische und Angewandte Mathematik, Einsteinstr. 62, D 48149 Münster, Germany
- MR Author ID: 974311
- Email: m.moeller@gmx.net
- Martin Benning
- Affiliation: Westfälische Wilhelms-Universität Münster, Institut für Numerische und Angewandte Mathematik, Einsteinstr. 62, D 48149 Münster, Germany
- Email: martin.benning@wwu.de
- Stanley Osher
- Affiliation: Department of Mathematics, University of California Los Angeles. Portola Plaza, Los Angeles, California 90095
- Email: sjo@math.ucla.edu
- Received by editor(s): February 23, 2011
- Received by editor(s) in revised form: July 11, 2011
- Published electronically: June 7, 2012
- Additional Notes: The work of MB and MB has been supported by the German Research Foundation DFG through the project Regularization with Singular Energies. M.M. and S.O. were supported by NSF grants DMS-0835863, DMS-0914561, DMS-0914856 and ONR grant N00014-08-1119. M.M. also acknowledges the support of the German Academic Exchange Service (DAAD)
- © Copyright 2012 American Mathematical Society
- Journal: Math. Comp. 82 (2013), 269-299
- MSC (2010): Primary 49M29, 90C25, 65F20, 65F22
- DOI: https://doi.org/10.1090/S0025-5718-2012-02599-3
- MathSciNet review: 2983025