Hinweise zum Einsatz der Google Suche
Personensuchezur unisono Personensuche
Veranstaltungssuchezur unisono Veranstaltungssuche
Katalog plus

Inverse Problem Matching Pursuits

  Matching Pursuits for Inverse Problems

Today, many different systems of trial functions are available for handling problems from the geosciences or medical imaging. Mathematically formulated, such problems discuss the approximation of functions on the sphere or the ball based on direct or indirect measurements. Spherical harmonics are a classical system of global trial functions with well-known possibilities of a physical interpretation but also with documented drawbracks e.g. in the case of heterogeneities in the data (with respect to the data quality or the data grid). On the other hand, numerous alternatives of localized trial functions have been constructed on the sphere and the ball  within the last three decades like Gaussian functions, Haar functions, Slepian functions, splines, and (multiple versions of) wavelets. They all have their intrinsic advantages and disadvantages.

The Regularized Functional Matching Pursuit (RFMP) is a novel algorithm that is able to combine different basis systems for solving an ill-posed inverse problem (e.g. in the geosciences or medical imaging). It is based on the Matching Pursuit (MP) by Mallat and Zhang (1993) and Vincent and Bengio (2002). The RFMP extends this algorithm in several aspects: (1) inverse problems can be handled, i.e. one can incorporate an equation which has to be solved, and the data and the solution need not be elements of the same space; (2) a regularization is included to treat ill-posed problems; (3) implementations for problems on non-Euclidean domains like a sphere or a ball have been realized.

The algorithm produces a sequence of approximations which converges to the regularized normal equation. This is done by iteratively minimizing a Tikhonov functional over a given set of trial functions, the dictionary. Numerical experiments show that the RFMP produces a sparse representation of the solution, i.e. it needs essentially less trial functions for achieving the same accuracy of the result than considered alternative approaches. This sparsity is achieved because the algorithm is able to combine different kinds of trial functions and because it chooses only those trial functions from the dictionary which are a best choice to reduce the (regularized) data misfit, i.e. the Tikhonov functional, fast. Up to now, several theorems concerning the convergence of the RFMP in the domain and in the range of the respective operator, the stability of the approximation as well as convergence rates have been developed.

The Regularized Orthogonal Functional Matching Pursuit (ROFMP) is an enhancement of the RFMP in the sense that it yields a representation of the solution in essentially less trial functions in comparison to the RFMP. This is achieved by a particular projection procedure which compensates for redundancies in the trial functions due to their non-orthogonality. The projection procedure is based on Vincent and Bengio (2002) and Pati et. al (1993). Numerical tests for a scenario of the (severely ill-posed) downward continuation of noisy gravity data from a satellite orbit to the Earth's surface demonstrated the applicability of the ROFMP and its particular features and advantages. 

Though these algorithms yield good results in our experiments, two practical issues seem problematic at first: the runtime cost for the minimization process in each iteration step and the a-priori choice of the dictionary.

The Regularized Weak Functional Matching Pursuit (RWFMP) incorporates a weak strategy based on Temlyakov (2000) to the RFMP. This approach implements a trade-off between necessary runtime for the minimization and accuracy of the minimization. In each step, the RWFMP chooses not necessarily a minimizer of the Tikhonov functional, but a trial function from the dictionary which is minimizing the Tikhonov functional 'well-enough'. Thus, the minimization process can be stopped earlier and runtime can be saved.

As experiments with the RFMP and the ROFMP have shown, the a-priori choice of the dictionary can crucially influence the results. Thus, the Learning Regularized (Orthogonal) Functional Matching Pursuit (LR(O)FMP) were developed. These algorithms admit an automatized determination (i.e. learning) of dictionary elements for a particular ill-posed inverse problem. The learnt dictionary elements can be used in future runs of the R(O)FMP. The learning approach can be viewed as a generalization of the R(O)FMP to an infinite set of trial functions. The minimization process is then realized with (non-linear) constrained optimization techniques. This also allows to choose a best basis out of an infinite dictionary including e.g. continuously parametrized radial basis functions.

Currently, together with Nico Sneeuw at the University of Stuttgart, we further develop the (L)IPMPs such that we are able to apply the algorithms to more realistic and larger data sets.