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.
- D. Fischer, V. Michel: Sparse regularization of inverse gravimetry – case study: spatial and temporal mass variations in South America, Inverse Problems, 28 (2012), 065012 (34pp), click here for download.
- D. Fischer, V. Michel: Automatic best-basis selection for geophysical tomographic inverse problems, Geophysical Journal International, 193 (2013), 1291-1299.
- D. Fischer, V. Michel: Inverting GRACE gravity data for local climate effects, Journal of Geodetic Science, 3 (2013), 151-162.
- M. Gutting, B. Kretz, V. Michel, R. Telschow: Study on parameter choice methods for the RFMP with respect to downward continuation, Frontiers in Applied Mathematics and Statistics, 3 (2017), Article 10.
- M. Kontak, V. Michel: A greedy algorithm for nonlinear inverse problems with an application to nonlinear inverse gravimetry, GEM: International Journal on Geomathematics, 9 (2018), 167-198.
- M. Kontak, V. Michel: The Regularized Weak Functional Matching Pursuit for linear inverse problems, Journal of Inverse and Ill-Posed Problems, 27 (2019), 317-340.
- V. Michel: RFMP - An Iterative Best Basis Algorithm for Inverse Problems in the Geosciences, in: Handbook of Geomathematics (W. Freeden, M.Z. Nashed, and T. Sonar, eds.), 2nd edition, Springer, Berlin, Heidelberg, 2015, pp. 2121-2147.
- V. Michel, S. Orzlowski: On the convergence theorem for the Regularized Functional Matching Pursuit (RFMP) algorithm, GEM: International Journal on Geomathematics, 8 (2017), 183-190. The article is also available via ShareIt.
- V. Michel, N. Schneider: A first approach to learning a best basis for gravity field modelling, submitted to GEM: International Journal on Geomathematics, arXiv: 1901.04222v2.
- V. Michel, R. Telschow: The regularized orthogonal functional matching pursuit for ill-posed inverse problems, SIAM Journal on Numerical Analysis, 54 (2016), 262-287.