Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 


An adaptive inverse scale space method for compressed sensing

Authors: Martin Burger, Michael Möller, Martin Benning and Stanley Osher
Journal: Math. Comp. 82 (2013), 269-299
MSC (2010): Primary 49M29, 90C25, 65F20, 65F22
Published electronically: June 7, 2012
MathSciNet review: 2983025
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. T. Blumensath and M. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmonic Anal. 27 (2009), 265-274. MR 2559726 (2010i:94048)
  • 3. M. Burger, A note on sparse reconstruction methods, J. Phys. Conference Series, no. 012002, 2008.
  • 4. M. Burger, K. Frick, S. Osher, and O. Scherzer, Inverse total variation flow, SIAM Multiscale Modelling and Simulation 6 (2007), 366-395. MR 2338487 (2008h:35212)
  • 5. M. Burger, G. Gilboa, S. Osher, and J. Xu, Nonlinear inverse scale space methods, Comm. Math. Sci. 4 (2006), 179-212. MR 2204083 (2006i:35177)
  • 6. M. Burger and S. Osher, A guide to TV zoo, preprint.
  • 7. M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), 109-135. MR 2354192 (2008k:94002)
  • 8. J. Cai, S. Osher, and Z. Shen, Convergence of the linearized Bregman iteration for $ \ell _1$-norm minimization, Math. Comp. 78 (2009), 2127-2136. MR 2521281 (2010k:65111)
  • 9. -, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), 1515-1536. MR 2501061 (2010e:65086)
  • 10. E. J. Candes and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2004), 4203-4215. MR 2243152 (2007b:94313)
  • 11. -, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inform. Theory 52 (2004), 5406-5425. MR 2300700 (2008c:94009)
  • 12. A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet schemes for elliptic operator equations-convergence rates, Math. Comp. 70 (2001), 27-75. MR 1803124 (2002h:65201)
  • 13. -, Adaptive wavelet methods II-beyond the elliptic case, Found. Comput. Math. 2 (2002), 203-245. MR 1907380 (2003f:65212)
  • 14. S. Dahlke, W. Dahmen, and K. Urban, Adaptive wavelet methods for saddle point problems-optimal convergence rates, SIAM J. Numer. Anal. 40 (2002), 1230-1262. MR 1951893 (2004g:42039)
  • 15. I. Daubechies, M. Defrise, and C. DeMol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math. 57 (2004), 1413-1457. MR 2077704 (2005k:65106)
  • 16. D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), 1289-1306. MR 2241189 (2007e:94013)
  • 17. D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $ \ell ^1$ minimization, Proc. Natl. Acad. Sci. USA 100 (2003), 2197-2202. MR 1963681 (2004c:94068)
  • 18. 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.
  • 19. I. Ekeland and R. Temam, Convex analysis and variational problems, corrected reprint edition ed., SIAM, Philadelphia, 1999. MR 1727362 (2000j:49001)
  • 20. S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing 12 (1993), 3397-3415.
  • 21. Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations: The fifteenth Dean Jacqueline B. Lewis memorial lectures, American Mathematical Society, 2001. MR 1852741 (2002j:43001)
  • 22. D. Needell and J. A. Tropp, Cosamp: Iterative signal recovery from incomplete and inaccurate samples, Applied and Computational Harmonic Analysis 26 (2009), 301-321. MR 2502366 (2010c:94018)
  • 23. D. Needell, J. A. Tropp, and R. Vershynin, Greedy signal recovery review, Proc. 42nd Asilomar Conf. Signals, Systems and Computers, 2008.
  • 24. 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.
  • 25. S. Osher, M. Burger, D. Goldfarb, and J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. Simul. 4 (2005), 460-489. MR 2162864 (2006c:49051)
  • 26. S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), 93-111. MR 2655902 (2011c:90098)
  • 27. 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.
  • 28. 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.
  • 29. J. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), 1030-1051. MR 2238069 (2007a:94064)
  • 30. J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory 53 (2007), 4655-4666. MR 2446929 (2009h:94042)
  • 31. Y. Wang and W. Yin, Sparse signal reconstruction via iterative support detection, SIAM J. Imaging Sci. 3 (2010), 462-491. MR 2679436 (2011h:94018)
  • 32. W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM J. Imaging Sciences 3 (2010), no. 4, pp. 856-877. MR 2735964 (2011j:68172)
  • 33. W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for $ \ell _1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), 143-168. MR 2475828 (2010f:90170)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 49M29, 90C25, 65F20, 65F22

Retrieve articles in all journals with MSC (2010): 49M29, 90C25, 65F20, 65F22

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

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

Martin Benning
Affiliation: Westfälische Wilhelms-Universität Münster, Institut für Numerische und Angewandte Mathematik, Einsteinstr. 62, D 48149 Münster, Germany

Stanley Osher
Affiliation: Department of Mathematics, University of California Los Angeles. Portola Plaza, Los Angeles, California 90095

Keywords: Compressed sensing, inverse scale space, sparsity, adaptivity, greedy methods
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)
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society