Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Multilevel preconditioning and adaptive sparse solution of inverse problems


Authors: Stephan Dahlke, Massimo Fornasier and Thorsten Raasch
Journal: Math. Comp. 81 (2012), 419-446
MSC (2010): Primary 41A25, 65F35, 65F50, 65N12, 65T60
DOI: https://doi.org/10.1090/S0025-5718-2011-02507-X
Published electronically: May 25, 2011
MathSciNet review: 2833502
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We are concerned with the efficient numerical solution of minimization problems in Hilbert spaces involving sparsity constraints. These optimizations arise, e.g., in the context of inverse problems. In this work we analyze an efficient variant of the well-known iterative soft-shrinkage algorithm for large or even infinite dimensional problems. This algorithm is modified in the following way. Instead of prescribing a fixed thresholding parameter, we use a decreasing thresholding strategy. Moreover, we use suitable variants of the adaptive schemes derived by Cohen, Dahmen and DeVore for the approximation of the infinite matrix-vector products. We derive a block multiscale preconditioning technique which allows for local well-conditioning of the underlying matrices and for extending the concept of restricted isometry property to infinitely labelled matrices. The combination of these ingredients gives rise to a numerical scheme that is guaranteed to converge with exponential rate, and which allows for a controlled inflation of the support size of the iterations. We also present numerical experiments that confirm the applicability of our approach which extends concepts from compressed sensing to large scale simulation.


References [Enhancements On Off] (What's this?)

  • 1. A. Beck and M. 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)
  • 2. T. Bonesky, S. Dahlke, P. Maass, and T. Raasch, Adaptive wavelet methods and sparsity reconstruction for inverse heat conduction problems, Adv. Comput. Math. 33 (2010), no. 4, 385-411.
  • 3. K. Bredies and D. A. Lorenz, Linear convergence of iterative soft-thresholding, J. Fourier Anal. Appl. 14 (2008), no. 5-6, 813-837. MR 2461608 (2010i:65109)
  • 4. E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203-4215. MR 2243152 (2007b:94313)
  • 5. -, Near optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406-5425. MR 2300700 (2008c:94009)
  • 6. A. Cohen, Numerical Analysis of Wavelet Methods., Studies in Mathematics and its Applications 32. Amsterdam: North-Holland., 2003. MR 1990555 (2004c:65178)
  • 7. A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods for elliptic operator equations -- Convergence rates, Math. Comp. 70 (2001), 27-75. MR 1803124 (2002h:65201)
  • 8. -, Adaptive wavelet methods II: Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203-245. MR 1907380 (2003f:65212)
  • 9. P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168-1200. MR 2203849 (2007g:94016)
  • 10. S. Dahlke, M. Fornasier, and T. Raasch, Adaptive frame methods for elliptic operator equations, Adv. Comput. Math. 27 (2007), no. 1, 27-63. MR 2317920 (2008c:65366)
  • 11. -, Multilevel preconditioning for adaptive sparse optimization, Preprint 25, DFG-SPP 1324, August 2009.
  • 12. S. Dahlke, M. Fornasier, T. Raasch, R. Stevenson, and M. Werner, Adaptive frame methods for elliptic operator equations: The steepest descent approach, IMA J. Numer. Anal. 27 (2007), no. 4, 717-740. MR 2371829 (2008i:65239)
  • 13. W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Numerica 6 (1997), 55-228. MR 1489256 (98m:65102)
  • 14. W. Dahmen and A. Kunoth, Multilevel preconditioning, Numer. Math 63 (1992), 315-344. MR 1186345 (93j:65065)
  • 15. W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential operators II: Matrix compression, Adv. Comput. Math. (1993), 259-335. MR 1242378 (95g:65149)
  • 16. -, Multiscale methods for pseudo-differential equations on smooth manifolds, Proceedings of the International Conference on Wavelets: Theory, Applications, and Algorithms, Academic Press, 1994, pp. 385-424. MR 1321437 (96c:65208)
  • 17. I. Daubechies, M. Defrise, and C. DeMol, An iterative thresholding algorithm for linear inverse problems, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413-1457. MR 2077704 (2005k:65106)
  • 18. R. A. DeVore, Nonlinear approximation, Acta Numerica 7 (1998), 51-150. MR 1689432 (2001a:41034)
  • 19. B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, Least angle regression, Ann. Statist. 32 (2004), no. 2, 407-499. MR 2060166 (2005d:62116)
  • 20. H.W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems., Mathematics and its Applications (Dordrecht). 375. Dordrecht: Kluwer Academic Publishers., 1996. MR 1408680 (97k:65145)
  • 21. M. Figueiredo, R. Nowak, and S. J. Wright, Sparse reconstruction by separable approximation, IEEE Trans. Signal Proc. (2009). MR 2650165 (2010m:94030)
  • 22. M. A. T. Figueiredo and R. D. Nowak, An EM algorithm for wavelet-based image restoration., IEEE Trans. Image Proc. 12 (2003), no. 8, 906-916. MR 2008658
  • 23. M. Fornasier and F. Pitolli, Adaptive iterative thresholding algorithms for magnetoenceophalography (MEG), J. Comput. Appl. Math. 221 (2008), no. 2, 386-395. MR 2457671 (2010a:65089)
  • 24. T. Gantumur, H. Harbrecht, and R. Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Math. Comp. 76 (2007), no. 258, 615-629. MR 2291830 (2008i:65310)
  • 25. G. H. Golub and C. F. van Loan, Matrix Computations, John Hopkins University Press, 1989.
  • 26. M. Grasmair, M. Haltmeier, and O. Scherzer, Sparse regularization with $ \ell^q$ penalty term, Inverse Problems 24 (2008), 055020 MR 2438955 (2010a:65086)
  • 27. -, Necessary and sufficient conditions for linear convergence of $ \ell_1$-regularization, preprint (2009).
  • 28. H. Harbrecht, T. Gantumur, and R. Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Mathematics of Computation 76 (2007), 615-629. MR 2291830 (2008i:65310)
  • 29. S. Jaffard, Propriétés des matrices ``bien localisées'' près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire 7 (1990), no. 5, 461-476. MR 1138533 (93h:47035)
  • 30. P.-G. Lemarié, Bases de'ondelettes sur les groupes de Lie stratifié, Bulletin de la Société Mathématique de France 117 (1989), no. 2, 213-232.
  • 31. A. K. Louis, Inverse und schlechtgestellte Probleme, Teubner, Stuttgart, 1989.
  • 32. M. Primbs, Stabile biorthogonale Spline-Waveletbasen auf dem Intervall, Dissertation, Universität Duisburg-Essen, 2006.
  • 33. R. Ramlau, G. Teschke, and M. Zhariy, A compressive Landweber iteration for solving ill-posed inverse problems, Inverse Problems 24 (2008), no. 6, 065013. MR 2456960 (2010a:65218)
  • 34. H. Rauhut, Compressive sensing and structured random matrices, Theoretical Foundations and Numerical Methods for Sparse Recovery (M. Fornasier, ed.), Radon Series Comp. Appl. Math., deGruyter, 2010.
  • 35. R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur effizienten Lösung grosser vollbesetzter Gleichungssysteme, Advances in Numerical Mathematics, Teubner Stuttgart, 1998. MR 1623209 (99f:65067)
  • 36. J.-L. Starck, E. J. Candès, and D. L. Donoho, Astronomical image representation by curvelet transform, Astronomy and Astrophysics 298 (2003), 785-800.
  • 37. J.-L. Starck, M. K. Nguyen, and F. Murtagh, Wavelets and curvelets for image deconvolution: a combined approach, Signal Proc. 83 (2003), 2279-2283.
  • 38. R. Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal 41 (2003), no. 3, 1074-1100. MR 2005196 (2004e:42062)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A25, 65F35, 65F50, 65N12, 65T60

Retrieve articles in all journals with MSC (2010): 41A25, 65F35, 65F50, 65N12, 65T60


Additional Information

Stephan Dahlke
Affiliation: Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Hans Meerwein Strasse, Lahnberge, 35032 Marburg, Germany
Email: dahlke@mathematik.uni-marburg.de

Massimo Fornasier
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstrasse 69, A-4040, Linz, Austria
Address at time of publication: Faculty of Mathematics, Technical University of Munich, Boltzmannstrasse 3, D-85748 Garching, Germany
Email: massimo.fornasier@ma.tum.de

Thorsten Raasch
Affiliation: Johannes Gutenberg-Universität, Institut für Mathematik, Staudingerweg 9, 55099 Mainz, Germany
Email: raasch@uni-mainz.de

DOI: https://doi.org/10.1090/S0025-5718-2011-02507-X
Keywords: Operator equations, multiscale methods, adaptive algorithms, sparse optimization and compressed sensing, multilevel preconditioning, wavelets, iterative thresholding, restricted isometry property.
Received by editor(s): August 14, 2009
Received by editor(s) in revised form: November 18, 2010
Published electronically: May 25, 2011
Additional Notes: The work of Stephan Dahlke was supported by Deutsche Forschungsgemeinschaft (DFG), Grant DA 360/12–1.
The work of Massimo Fornasier was supported by the FWF project Y 432-N15 START-Preis “Sparse Approximation and Optimization in High Dimensions” and Deutsche Forschungsgemeinschaft (DFG), Grant DA 360/12–1.
The work of Thorsten Raasch was supported by Deutsche Forschungsgemeinschaft (DFG), Grants DA 360/7–1 and DA 360/11–1.
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society