Greedy solution of ill-posed problems: error bounds and exact inversion

DOI10.1088/0266-5611/25/11/115017MaRDI QIDQ3652584zbMATH OpenOpenAlexFDO

Authors Loïc Denis, Dirk A. Lorenz, Dennis Trede

Publication date 18 December 2009

Published in Inverse Problems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.0154

zbMATH Keywords

digital holomorphyerror boundsgreedy algorithmill-posed inverse problemsmass spectrometrynoisy signalsnumerical examplessparse approximation problems

Mathematics Subject Classification ID

Boundary value problems for second-order elliptic equations (35J25) Ill-posed problems for PDEs (35R25) Inverse problems for PDEs (35R30) Linear operators and ill-posed problems, regularization (47A52) Numerical solutions to equations with linear operators (65J10) Numerical solutions of ill-posed problems in abstract spaces; regularization (65J20) Numerical solution to inverse problems in abstract spaces (65J22)

Abstract: The orthogonal matching pursuit (OMP) is an algorithm to solve sparse approximation problems. Sufficient conditions for exact recovery are known with and without noise. In this paper we investigate the applicability of the OMP for the solution of ill-posed inverse problems in general and in particular for two deconvolution examples from mass spectrometry and digital holography respectively. In sparse approximation problems one often has to deal with the problem of redundancy of a dictionary, i.e. the atoms are not linearly independent. However, one expects them to be approximatively orthogonal and this is quantified by the so-called incoherence. This idea cannot be transfered to ill-posed inverse problems since here the atoms are typically far from orthogonal: The ill-posedness of the operator causes that the correlation of two distinct atoms probably gets huge, i.e. that two atoms can look much alike. Therefore one needs conditions which take the structure of the problem into account and work without the concept of coherence. In this paper we develop results for exact recovery of the support of noisy signals. In the two examples in mass spectrometry and digital holography we show that our results lead to practically relevant estimates such that one may check a priori if the experimental setup guarantees exact deconvolution with OMP. Especially in the example from digital holography our analysis may be regarded as a first step to calculate the resolution power of droplet holography.

Recommendations

• Sparsity and incoherence in orthogonal matching pursuit
• Orthogonal matching pursuit under the restricted isometry property
• Greed is Good: Algorithmic Results for Sparse Approximation
• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• A sufficient condition for sparse signals' exact recovery by using OMP algorithm

Cited in

(1)

• Regularized sparse representation for image deconvolution

This page was built for publication: Greedy solution of ill-posed problems: error bounds and exact inversion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652584)