Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
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

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
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: http://dx.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



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia