FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems

Tan Bui-Thanh; Quoc P.  Nguyen

doi:10.3934/ipi.2016028

Article Contents

2016, Volume 10, Issue 4: 943-975. Doi: 10.3934/ipi.2016028

This issue Previous Article Imaging with electromagnetic waves in terminating waveguides Next Article Team organization may help swarms of flies to become invisible in closed waveguides

FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems

Tan Bui-Thanh^1, and
Quoc P. Nguyen^2,

1.
Department of Aerospace Engineering and Engineering Mechanics, Institute for Computational Engineering & Sciences, The University of Texas at Austin, Austin, TX 78712
2.
Department of Petroleum and Geosystems Engineering, The University of Texas at Austin, Austin, TX 78712

Received: August 2015

Revised: May 2016

Published: November 2016

Abstract / Introduction Related Papers Cited by

Abstract

We present a systematic construction of FEM-based dimension-independent (discretization-invariant) Markov chain Monte Carlo (MCMC) approaches to explore PDE-constrained Bayesian inverse problems in infinite dimensional parameter spaces. In particular, we consider two frameworks to achieve this goal: Metropolize-then-discretize and discretize-then-Metropolize. The former refers to the method of discretizing function-space MCMC methods. The latter, on the other hand, first discretizes the Bayesian inverse problem and then proposes MCMC methods for the resulting discretized posterior probability density. In general, these two frameworks do not commute, that is, the resulting finite dimensional MCMC algorithms are not identical. The discretization step of the former may not be trivial since it involves both numerical analysis and probability theory, while the latter, perhaps ``easier'', may not be discretization-invariant using traditional approaches. This paper constructively develops finite element (FEM) discretization schemes for both frameworks and shows that both commutativity and discretization-invariance are attained. In particular, it shows how to construct discretize-then-Metropolize approaches for both Metropolis-adjusted Langevin algorithm and the hybrid Monte Carlo method that commute with their Metropolize-then-discretize counterparts. The key that enables this achievement is a proper FEM discretization of the prior, the likelihood, and the Bayes' formula, together with a correct definition of quantities such as the gradient and the covariance matrix in discretized finite dimensional parameter spaces. The implication is that practitioners can take advantage of the developments in this paper to straightforwardly construct discretization-invariant discretize-then-Metropolize MCMC for large-scale inverse problems. Numerical results for one- and two-dimensional elliptic inverse problems with up to $17899$ parameters are presented to support the proposed developments.

Keywords:

Mathematics Subject Classification: Primary: 62F15, 35Q62, 35R30; Secondary: 65C60.

Citation:

Related Papers

Cited by

References

[1]	A. Beskos, N. Pillai, G. Roberts, J-M Sanz-Serna and A. Stuart, Optimal tuning of the hybrid Monte Carlo algorithm, Bernoulli, 19 (2013), 1501-1534.doi: 10.3150/12-BEJ414.
[2]	A. Beskos, F. J. Pinski, J. M. Sanz-Serna and A. M. Stuart, Hybrid Monte Carlo on Hilbert spaces, Stochastic Processes and their Applications, 121 (2011), 2201-2230.doi: 10.1016/j.spa.2011.06.003.
[3]	A. Beskos and A. M. Stuart, MCMC methods for sampling function space, in Invited Lectures: Sixth International Congress on Industrial and Applied Mathematics, ICIAM 2007, R. Jeltsch and G. Wanner, eds., European Mathematical Society, 2009, 337-364.doi: 10.4171/056-1/16.
[4]	A. Borzí and V. Schulz, Computational Optimization of Systems Governed by Partial Differential Equations, SIAM, 2012.
[5]	T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part I: Inverse shape scattering of acoustic waves, Inverse Problems, 28 (2012), 055001, 32pp.doi: 10.1088/0266-5611/28/5/055001.
[6]	_________, Analysis of the Hessian for inverse scattering problems. Part II: Inverse medium scattering of acoustic waves, Inverse Problems, 28 (2012), 055002.
[7]	_________, Analysis of the Hessian for inverse scattering problems. Part III: Inverse medium scattering of electromagnetic waves. Inverse Problems and Imaging, 2013.
[8]	_________, Randomized maximum likelihood sampling for large-scale Bayesian inverse problems, In preparation, 2013.
[9]	_________, An analysis of infinite dimensional Bayesian inverse shape acoustic scattering and its numerical approximation, SIAM Journal of Uncertainty Quantification, 2 (2014), 203-222.doi: 10.1137/120894877.
[10]	T. Bui-Thanh, O. Ghattas, J. Martin and G. Stadler, A computational framework for infinite-dimensional Bayesian inverse problems Part I: The linearized case, with application to global seismic inversion, SIAM Journal on Scientific Computing, 35 (2013), A2494-A2523.doi: 10.1137/12089586X.
[11]	T. Bui-Thanh and M. A. Girolami, Solving large-scale PDE-constrained Bayesian inverse problems with Riemann manifold Hamiltonian Monte Carlo, Inverse Problems, Special Issue, 30 (2014), 114014, 23pp.doi: 10.1088/0266-5611/30/11/114014.
[12]	F. P. Casey, J. J. Waterfall, R. N. Gutenkunst, C. R. Myers and J. P. Sethna, Variational method for estimating the rate of convergence of Marko-chain Monte Carlo algorithms, Phy. Rev. E., 78 (2008), 046704.
[13]	P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, New York, 1978.
[14]	S. L. Cotter, G. O. Roberts, A. M. Stuart and D. White, MCMC methods for functions: Modifying old algorithms to make them faster, Statistical Science, 28 (2013), 424-446.doi: 10.1214/13-STS421.
[15]	M. Dashti, K. J. H. Law, A. M. Stuart and J. Voss, MAP estimators and their consistency in Bayesian nonparametric inverse problems, Inverse Problems, 29 (2013), 095017, 27pp.doi: 10.1088/0266-5611/29/9/095017.
[16]	S. Duane, A. D. Kennedy, B. Pendleton and D. Roweth, Hybrid Monte Carlo, Phys. Lett. B, 195 (1987), 216-222.doi: 10.1016/0370-2693(87)91197-X.
[17]	J. N. Franklin, Well-posed stochastic extensions of ill-posed linear problems, Journal of Mathematical Analysis and Applications, 31 (1970), 682-716.doi: 10.1016/0022-247X(70)90017-X.
[18]	A. Gelman, G. O. Roberts and W. R. Gilks, Efficient Metropolis jumping rules, in Bayesian Statistics, J. M. Bernardo, J. O. Berger, A. P. Dawid, and A. F. M. Smith, eds., Oxford Univ Press, 5 (1996), 599-607.
[19]	M. Girolami and B. Calderhead, Riemann manifold Langevin and Hamiltonian Monte Carlo methods, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2011), 123-214.doi: 10.1111/j.1467-9868.2010.00765.x.
[20]	M. D. Gunzburger, Perspectives in Flow Control and Optimization, SIAM, Philadelphia, 2003.
[21]	H. Haario, M. Laine, A. Miravete and E. Saksman, DRAM: Efficient adaptive MCMC, Statistics and Computing, 16 (2006), 339-354.doi: 10.1007/s11222-006-9438-0.
[22]	M. Hairer, A. M. Stuart and J. Voss, Analysis of SPDEs arising in path sampling. part II: The nonlinear case, Annals of Applied Probability, 17 (2007), 1657-1706.doi: 10.1214/07-AAP441.
[23]	W. Keith Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57 (1970), 97-109.doi: 10.1093/biomet/57.1.97.
[24]	E. Herbst, Gradient and Hessian-based MCMC for DSGE models, (2010). Unpublished manuscript.
[25]	M. Ilić, F. Liu, I. Turner and V. Anh, Numerical approximation of a fractional-in-space diffusion equation, Frac. Calc. and A Anal., 8 (2005), 323-341.
[26]	S. Lasanen, Discretizations of Generalized Random Variables with Applications to Inverse Problems, PhD thesis, University of Oulu, 2002.
[27]	M. S. Lehtinen, L. Päivärinta and E. Somersalo, Linear inverse problems for generalized random variables, Inverse Problems, 5 (1989), 599-612.doi: 10.1088/0266-5611/5/4/011.
[28]	F. Lindgren, H. Rue and J. Lindström, An explicit link between gaussian fields and gaussian markov random fields: The stochastic partial differential equation approach, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2011), 423-498.doi: 10.1111/j.1467-9868.2011.00777.x.
[29]	J. Martin, L. C. Wilcox, C. Burstedde and O. Ghattas, A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM Journal on Scientific Computing, 34 (2012), A1460-A1487.doi: 10.1137/110845598.
[30]	N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21 (1953), 1087-1092.doi: 10.1063/1.1699114.
[31]	R. M. Neal, Handbook of Markov Chain Monte Carlo, Chapman & Hall / CRC Press, 2010, ch. MCMC using Hamiltonian dynamics.
[32]	J. Nocedal and S. J. Wright, Numerical Optimization, Springer Verlag, Berlin, Heidelberg, New York, second ed., 2006.
[33]	M. Ottobre, N. S. Pillai, F. J. Pinski and A. M. Stuart, A function space HMC algorithm with second order langevin diffusion limit, Bernoulli, 22 (2016), 60-106, arXiv, arXiv:1308.0543 (2014).doi: 10.3150/14-BEJ621.
[34]	P. Piiroinen, Statistical Measurements, Experiments, and Applications, PhD thesis, Department of Mathematics and Statistics, University of Helsinki, 2005.
[35]	G. Da Prato and J. Zabczyk, Stochastic Equations in Infinite Dimensions, Cambidge University Press, 1992.doi: 10.1017/CBO9780511666223.
[36]	Y. Qi and T. P. Minka, Hessian-based Markov chain Monte-Carlo algorithms, in First Cape Cod Workshop on Monte Carlo Methods, Cape Cod, MA, USA, September 2002.
[37]	C. P. Robert and G. Casella, Monte Carlo Statistical Methods (Springer Texts in Statistics), Springer-Verlag, New York, 2004.doi: 10.1007/978-1-4757-4145-2.
[38]	G. O. Roberts, A. Gelman and W. R. Gilks, Weak convergence and optimal scaling of random walk Metropolis algorithms, The Annals of Applied Probability, 7 (1997), 110-120.doi: 10.1214/aoap/1034625254.
[39]	G. O. Roberts and J. S. Rosenthal, Optimal scaling of discrete approximations to Langevin diffusions, J. R. Statist. Soc. B, 60 (1997), 255-268.doi: 10.1111/1467-9868.00123.
[40]	J. Rosenthal, Optimal proposal distributions and adaptive MCMC, in Handbook of Markov chain Monte Carlo, Steve Brooks, Andrew Gelman, Galin L. Jones, and Xiao-Li Meng, eds., CRC Press, 2011, 93-112.
[41]	P. J. Rossky, J. D. Doll and H. L. Friedman, Brownian dynamics as smart Monte Carlo simulation, J. Chem. Phys., 69 (1978), p. 4268.doi: 10.1063/1.436415.
[42]	D. P. Simpson, Krylov subpsace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous Diffusion, PhD thesis, School of Mathematical Sciences Qeensland University of Technology, 2008.
[43]	A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559.doi: 10.1017/S0962492910000061.
[44]	A. M. Stuart, J. Voss and P. Wiberg, Conditional path sampling of SDEs and the Langevin MCMC method, Communications in Mathematical Sciences, 2 (2004), 685-697.doi: 10.4310/CMS.2004.v2.n4.a7.
[45]	L. Tierney, A note on Metropolis-Hastings kernels for general state spaces, Annals of Applied Probability, 8 (1998), 1-9.doi: 10.1214/aoap/1027961031.
[46]	C. Vacar, J.-F. Giovannelli and Y. Berthoumieu, Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (2011), 3964-3967.doi: 10.1109/ICASSP.2011.5947220.
[47]	B. Vexler, Adaptive finite element methods for parameter identification problems, Model Based Parameter Estimation, Volume 4 of the series Contributions in Mathematical and Computational Sciences, (2012), 31-54.doi: 10.1007/978-3-642-30367-8_2.
[48]	C. R. Vogel, Computational Methods for Inverse Problems, Frontiers in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002.doi: 10.1137/1.9780898717570.
[49]	Y. Zhang and C. Sutton, Quasi-Newton methods for Markov chain Monte Carlo, in Advances in Neural Information Processing Systems, J. Shawe-Taylor, R. S. Zemel, P. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, eds., vol. 24, 2011.