Multilevel Preconditioning and Adaptive Sparse Solution of Inverse Problems
We are concerned with the efficient numerical solutaion of minimization problems in Hilbert spaces involving sparsity constraints. These optimization problems arise, e.g., in the context of inverse problems. We analyze a very efficient variant of the well-known iterative soft shrinkage algorithm for large or even infinite dimesnional problems. This algorithm is modified in the following way. Instead of prescribing a fixed threshold parameter, we use a decreasing thresholding strategy. Moreover, we use suitable adaptive schemes for the approximation of the infinite matrix-vector products. We also 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 careful combination of these ingredients gives rise to numerical schemes that are guaranteed to cnverge with esponential rate, and which allow for the controlled inflation of the support size of the iterations. We also present numerical experiments that confirm the applicability of our approach.
(Joint work with M. Fornasier and T. Raasch)