A Caltech Library Service

Complexity analysis of accelerated MCMC methods for Bayesian inversion

Hoang, Viet Ha and Schwab, Christoph and Stuart, Andrew M. (2013) Complexity analysis of accelerated MCMC methods for Bayesian inversion. Inverse Problems, 29 (8). Art No. 085010. ISSN 0266-5611. doi:10.1088/0266-5611/29/8/085010.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The Bayesian approach to inverse problems, in which the posterior probability distribution on an unknown field is sampled for the purposes of computing posterior expectations of quantities of interest, is starting to become computationally feasible for partial differential equation (PDE) inverse problems. Balancing the sources of error arising from finite-dimensional approximation of the unknown field, the PDE forward solution map and the sampling of the probability space under the posterior distribution are essential for the design of efficient computational Bayesian methods for PDE inverse problems. We study Bayesian inversion for a model elliptic PDE with an unknown diffusion coefficient. We provide complexity analyses of several Markov chain Monte Carlo (MCMC) methods for the efficient numerical evaluation of expectations under the Bayesian posterior distribution, given data δ. Particular attention is given to bounds on the overall work required to achieve a prescribed error level ε. Specifically, we first bound the computational complexity of 'plain' MCMC, based on combining MCMC sampling with linear complexity multi-level solvers for elliptic PDE. Our (new) work versus accuracy bounds show that the complexity of this approach can be quite prohibitive. Two strategies for reducing the computational complexity are then proposed and analyzed: first, a sparse, parametric and deterministic generalized polynomial chaos (gpc) 'surrogate' representation of the forward response map of the PDE over the entire parameter space, and, second, a novel multi-level Markov chain Monte Carlo strategy which utilizes sampling from a multi-level discretization of the posterior and the forward PDE. For both of these strategies, we derive asymptotic bounds on work versus accuracy, and hence asymptotic bounds on the computational complexity of the algorithms. In particular, we provide sufficient conditions on the regularity of the unknown coefficients of the PDE and on the approximation methods used, in order for the accelerations of MCMC resulting from these strategies to lead to complexity reductions over 'plain' MCMC algorithms for the Bayesian inversion of PDEs.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Schwab, Christoph0000-0002-4046-987X
Additional Information:© 2013 IOP. Received 10 July 2012, in final form 30 April 2013. Published 25 July 2013. VHH is supported by a start up grant from Nanyang Technological University, CS acknowledges partial support by the Swiss National Science Foundation and by the European Research Council under grant ERC AdG 247277—STAHDPDE and AMS is grateful to EPSRC (UK) and ERC for financial support. The authors are also particularly grateful to Daniel Gruhlke, who shared his ideas concerning multi-level MCMC methods for conditioned diffusion processes during a visit to AS at Warwick in September 2011, and to Rob Scheichl who found an error in an earlier pre-print of the multi-level MCMC material, leading us to consider the improved analysis contained herein.
Funding AgencyGrant Number
Nanyang Technological UniversityUNSPECIFIED
Swiss National Science Foundation (SNSF)UNSPECIFIED
European Research Council (ERC)AdG 247277—STAHDPDE
Engineering and Physical Sciences Research Council (EPSRC)UNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Andrew StuartJ102
Issue or Number:8
Record Number:CaltechAUTHORS:20160727-163339156
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69262
Deposited By: Linda Taddeo
Deposited On:28 Jul 2016 21:51
Last Modified:12 Jul 2022 19:48

Repository Staff Only: item control page