Complexity analysis of accelerated MCMC methods for Bayesian inversion
From MaRDI portal
Abstract: We study Bayesian inversion for a model elliptic PDE with 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 multilevel 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 (MLMCMC) strategy which utilizes sampling from a multilevel discretization of the posterior and of 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 Bayesian inversion of PDEs.}
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.
Recommendations
- Analysis of a multilevel Markov chain Monte Carlo finite element method for Bayesian inversion of log-normal diffusions
- Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors
- Stochastic spectral methods for efficient Bayesian solution of inverse problems
- Quasi-Monte Carlo and multilevel Monte Carlo methods for computing posterior expectations in elliptic inverse problems
- Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
Cited in
(72)- Itô-SDE MCMC method for Bayesian characterization of errors associated with data limitations in stochastic expansion methods for uncertainty quantification
- Bayesian inverse problems with Monte Carlo forward models
- Multilevel ensemble Kalman filtering for spatio-temporal processes
- A dynamic bi-orthogonal field equation approach to efficient Bayesian inversion
- Optimal Bayesian experimental design for electrical impedance tomography in medical imaging
- A Bayesian level set method for the shape reconstruction of inverse scattering problems in elasticity
- Markov chain simulation for multilevel Monte Carlo
- Statistical guarantees for Bayesian uncertainty quantification in nonlinear inverse problems with Gaussian process priors
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Bayesian multiscale deep generative model for the solution of high-dimensional inverse problems
- On the convergence of the Laplace approximation and noise-level-robustness of Laplace-based Monte Carlo methods for Bayesian inverse problems
- Accelerating Metropolis-within-Gibbs sampler with localized computations of differential equations
- A Bayesian estimation method for variational phase-field fracture problems
- Central limit theorems for multilevel Monte Carlo methods
- Approximation and sampling of multivariate probability distributions in the tensor train decomposition
- Hessian-based adaptive sparse quadrature for infinite-dimensional Bayesian inverse problems
- Dimension-independent likelihood-informed MCMC
- Sparse-grid, reduced-basis Bayesian inversion: nonaffine-parametric nonlinear equations
- Sparse variational Bayesian approximations for nonlinear inverse problems: applications in nonlinear elastography
- Sparse-grid, reduced-basis Bayesian inversion
- Multilevel Markov chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation
- Acoustic full waveform inversion with Hamiltonian Monte Carlo method
- Multilevel ensemble Kalman filtering
- Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors
- Multilevel sequential Monte Carlo: Mean square error bounds under verifiable conditions
- Multilevel higher-order quasi-Monte Carlo Bayesian estimation
- Higher-order quasi-Monte Carlo for Bayesian shape inversion
- Multilevel sequential Monte Carlo with dimension-independent likelihood-informed proposals
- FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems
- Stochastic Galerkin Finite Element Method with Local Conductivity Basis for Electrical Impedance Tomography
- A Hierarchical Multilevel Markov Chain Monte Carlo Algorithm with Applications to Uncertainty Quantification in Subsurface Flow
- Multilevel Particle Filters
- Bayesian static parameter estimation for partially observed diffusions via multilevel Monte Carlo
- Accuracy of some approximate Gaussian filters for the Navier-Stokes equation in the presence of model error
- Multilevel Markov chain Monte Carlo for Bayesian inversion of parabolic partial differential equations under Gaussian prior
- Stein variational reduced basis Bayesian inversion
- Analysis of a multilevel Markov chain Monte Carlo finite element method for Bayesian inversion of log-normal diffusions
- Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
- Scalable Optimization-Based Sampling on Function Space
- Multilevel Quasi-Monte Carlo Uncertainty Quantification for Advection-Diffusion-Reaction
- Stochastic spectral methods for efficient Bayesian solution of inverse problems
- Deep neural network expression of posterior expectations in Bayesian PDE inversion
- Multilevel Markov Chain Monte Carlo
- Quasi-Monte Carlo and multilevel Monte Carlo methods for computing posterior expectations in elliptic inverse problems
- Multilevel sequential Monte Carlo samplers
- Bayesian inverse problems for recovering coefficients of two scale elliptic equations
- Bayesian inversion for electromyography using low-rank tensor formats
- Analysis of nested multilevel Monte Carlo using approximate normal random variables
- Sequential Monte Carlo methods for Bayesian elliptic inverse problems
- Advanced Multilevel Monte Carlo Methods
- A Benchmark for the Bayesian Inversion of Coefficients in Partial Differential Equations
- A Bayesian scheme for reconstructing obstacles in acoustic waveguides
- Identifying a fractional order and a time-dependent coefficient in a time-fractional diffusion wave equation
- Bayesian inversion of log-normal eikonal equations
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- (Non)-penalized multilevel methods for non-uniformly log-concave distributions
- scientific article; zbMATH DE number 7709350 (Why is no real title available?)
- A randomized multi-index sequential Monte Carlo method
- Multilevel dimension-independent likelihood-informed MCMC for large-scale inverse problems
- A low-rank solver for parameter estimation and uncertainty quantification in time-dependent systems of partial differential equations
- Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
- Numerical realization of the Bayesian inversion accelerated using surrogate models.
- A hybrid two-level MCMC framework to accelerate posterior mean estimation with deep learning surrogates for Bayesian inverse problems
- Unbiased parameter estimation for Bayesian inverse problems
- Bayesian approach for two-dimensional interior inverse scattering problem in elasticity
- Derivative-informed neural operator acceleration of geometric MCMC for infinite-dimensional Bayesian inverse problems
- Bayesian inversion for electrical impedance tomography by sparse interpolation
- Convergence speed and approximation accuracy of numerical MCMC
- Local sensitivity analysis for Bayesian inverse problems
- Multilevel Monte Carlo for a class of partially observed processes in neuroscience
- Bayesian inversion of log-normal eikonal equations on Riemannian and Randers manifolds
- Numerical analysis of Bayesian inverse problems of spectral fractional elliptic equations under log-normal setting
This page was built for publication: Complexity analysis of accelerated MCMC methods for Bayesian inversion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2866183)
