Complexity analysis of accelerated MCMC methods for Bayesian inversion (Q2866183)

The authors propose a ``complexity analysis of several Monte Carlo methods under the Bayesian posterior distribution given data''. They give ``several error bounds on the overall work required to achieve a prescribed error level.'' They first bound ``the complexity of the plain Markov chain Monte Carlo (MCMC) method, based on combining Monte Carlo sampling with linear complexity multi-level solvers for elliptic partial differential equations''. The error analysis shows that ``the complexity of this approach can be quite prohibitive.'' Then, two approaches are proposed to reduce the computational complexity: ``first, a sparse, parametric and deterministic generalized polynomial chaos representation method, and second, a novel multi-level MCMC method.'' Then, asymptotic bounds on work versus accuracy and asymptotic bounds on the computational complexity are derived for both methods.