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
Published electronically: May 25, 2011
MathSciNet review: 2833502
Full-text PDF Free Access

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?)


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

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

Thorsten Raasch
Affiliation: Johannes Gutenberg-Universität, Institut für Mathematik, Staudingerweg 9, 55099 Mainz, Germany

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