  Deterministic interpolation and quadrature methods are often unsuitable to
address Bayesian inverse problems depending on computationally expensive
forward mathematical models. While interpolation may give precise posterior
approximations, deterministic quadrature is usually unable to efficiently
investigate an informative and thus concentrated likelihood. This leads to a
large number of required expensive evaluations of the mathematical model. To
overcome these challenges, we formulate and test a multilevel adaptive sparse
Leja algorithm. At each level, adaptive sparse grid interpolation and
quadrature are used to approximate the posterior and perform all quadrature
operations, respectively. Specifically, our algorithm uses coarse
discretizations of the underlying mathematical model to investigate the
parameter space and to identify areas of high posterior probability. Adaptive
sparse grid algorithms are then used to place points in these areas, and ignore
other areas of small posterior probability. The points are weighted Leja
points. As the model discretization is coarse, the construction of the sparse
grid is computationally efficient. On this sparse grid, the posterior measure
can be approximated accurately with few expensive, fine model discretizations.
The efficiency of the algorithm can be enhanced further by exploiting more than
two discretization levels. We apply the proposed multilevel adaptive sparse
Leja algorithm in numerical experiments involving elliptic inverse problems in
2D and 3D space, in which we compare it with Markov chain Monte Carlo sampling
and a standard multilevel approximation.
