An adaptive inverse scale space method for compressed sensing

Burger, Martin; Möller, Michael; Benning, Martin; Osher, Stanley

doi:10.1090/S0025-5718-2012-02599-3

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