×

Localization for MCMC: sampling high-dimensional posterior distributions with local structure. (English) Zbl 1451.65011

Summary: We investigate how ideas from covariance localization in numerical weather prediction can be used in Markov chain Monte Carlo (MCMC) sampling of high-dimensional posterior distributions arising in Bayesian inverse problems. To localize an inverse problem is to enforce an anticipated “local” structure by (i) neglecting small off-diagonal elements of the prior precision and covariance matrices; and (ii) restricting the influence of observations to their neighborhood. For linear problems we can specify the conditions under which posterior moments of the localized problem are close to those of the original problem. We explain physical interpretations of our assumptions about local structure and discuss the notion of high dimensionality in local problems, which is different from the usual notion of high dimensionality in function space MCMC. The Gibbs sampler is a natural choice of MCMC algorithm for localized inverse problems and we demonstrate that its convergence rate is independent of dimension for localized linear problems. Nonlinear problems can also be tackled efficiently by localization and, as a simple illustration of these ideas, we present a localized Metropolis-within-Gibbs sampler. Several linear and nonlinear numerical examples illustrate localization in the context of MCMC samplers for inverse problems.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
65C05 Monte Carlo methods
62M40 Random fields; image analysis
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Agapiou, S.; Papaspiliopoulos, O.; Sanz-Alonso, D.; Stuart, A., Importance sampling: computational complexity and intrinsic dimension, Stat. Sci., 32, 405-431 (2017) · Zbl 1442.62026
[2] Auligné, T.; Ménétrier, B.; Lorenc, A.; Buehner, M., Ensemble-variational integrated localized data assimilation, Mon. Weather Rev., 144, 3677-3696 (2016)
[3] Bardsley, J., MCMC-based image reconstruction with uncertainty quantification, SIAM J. Sci. Comput., 34, A1316-A1332 (2012) · Zbl 1246.15022
[4] Beskos, A.; Pillai, N.; Roberts, G.; Sanz-Serna, J.-M.; Stuart, A., Optimal tuning of the hybrid Monte Carlo algorithm, Bernoulli, 19, 1501-1534 (2013) · Zbl 1287.60090
[5] Beskos, A.; Roberts, G.; Stuart, A., Optimal scalings for local Metropolis-Hastings chains on nonproduct targets in high dimensions, Ann. Appl. Probab., 19, 863-898 (2009) · Zbl 1172.60328
[6] Bickel, P.; Levina, E., Regularized estimation of large covariance matrices, Ann. Stat., 36, 199-227 (2008) · Zbl 1132.62040
[7] Bickel, P.; Lindner, M., Approximating the inverse of banded matrices by banded matrices with applications to probability and statistics, Theory Probab. Appl., 56, 1-20 (2012) · Zbl 1241.60017
[8] Bui-Thanh, T.; Ghattas, O.; Martin, J.; Stadler, G., A computational framework for infinite-dimensional Bayesian inverse problems. Part I: the linearized case, with application to global seismic inversion, SIAM J. Sci. Comput., 36, A2494-A2523 (2013) · Zbl 1287.35087
[9] Chorin, A.; Morzfeld, M., Conditions for successful data assimilation, J. Geophys. Res., 118, 11,522-11,533 (2013)
[10] Christen, J.; Fox, C., A general purpose sampling algorithm for continuous distributions (the t-walk), Bayesian Anal., 5, 263-282 (2010) · Zbl 1330.62007
[11] Christensen, O. F.; Roberts, G. O.; Rosenthal, J. S., Scaling limits for the transient phase of local Metropolis-Hastings algorithms, J. R. Stat. Soc., Ser. B, Stat. Methodol., 67, 253-268 (2005) · Zbl 1075.65012
[12] Cotter, S.; Roberts, G.; Stuart, A.; White, D., MCMC methods for functions: modifying old algorithms to make them faster, Stat. Sci., 28, 424-446 (2013) · Zbl 1331.62132
[13] Cui, T.; Law, K. J.H.; Marzouk, Y. M., Dimension-independent likelihood-informed MCMC, J. Comput. Phys., 304, 109-137 (2016) · Zbl 1349.65009
[14] Cui, T.; Martin, J.; Marzouk, Y. M.; Solonen, A.; Spantini, A., Likelihood-informed dimension reduction for nonlinear inverse problems, Inverse Probl., 29, Article 114015 pp. (2014) · Zbl 1310.62030
[15] Cui, T.; Marzouk, Y. M.; Willcox, K., Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction, J. Comput. Phys., 315, 363-387 (2016) · Zbl 1349.65189
[16] Duane, S.; Kennedy, A.; Pendleton, B.; Roweth, D., Hybrid Monte Carlo, Phys. Lett. B, 195, 216-222 (1987)
[17] Flath, H.; Wilcox, L.; Akçelik, V.; Hill, J.; van Bloemen Waander, B.; Ghattas, O., Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations, SIAM J. Sci. Comput., 33, 407-432 (2011) · Zbl 1229.65174
[18] Foreman-Mackey, D.; Conley, A.; Meierjurgen Farr, W.; Hogg, D. W.; Long, D.; Marshall, P.; Price-Whelan, A.; Sanders, J.; Zuntz, J., emcee: the MCMC hammer (Mar. 2013), Astrophysics Source Code Library
[19] Fowler, M.; Howard, M.; Luttman, A.; Mitchell, S.; Webb, T., A stochastic approach to quantifying the blur with uncertainty estimation for high-energy X-ray imaging systems, Inverse Probl. Sci. Eng., 34, 353-371 (2016)
[20] Fox, C.; Parker, A., Accelerated Gibbs sampling of normal distributions using matrix splittings and polynomials, Bernoulli, 23, 3711-3743 (2017) · Zbl 1457.62085
[21] Galli, A.; Gao, H., Rate of convergence of the Gibbs sampler in the Gaussian case, Math. Geol., 33, 653-677 (2001) · Zbl 1011.86008
[22] Gaspari, G.; Cohn, S., Construction of correlation functions in two and three dimensions, Q. J. R. Meteorol. Soc., 125, 723-757 (1999)
[23] Gilks, W.; Richardson, S.; Spiegelhalter, D., Introducing Markov chain Monte Carlo, (Gilks, W.; Richardson, S.; Spiegelhalter, D., Markov Chain Monte Carlo in Practice (1996), Srpinger-Science+Business Media), 1-20, ch. 1 · Zbl 0845.60072
[24] Girolami, M.; Calderhead, B., Riemann manifold Langevin and Hamiltonian Monte Carlo methods, J. R. Stat. Soc. B, 73, 123-214 (2011) · Zbl 1411.62071
[25] Goodman, J.; Sokal, A. D., Multigrid Monte Carlo method. Conceptual foundation, Phys. Rev. D, 40, 2035-2071 (1989)
[26] Goodman, J.; Weare, J., Ensemble samplers with affine invariance, Commun. Appl. Math. Comput. Sci., 5, 65-80 (2010) · Zbl 1189.65014
[27] Hairer, M.; Stuart, A. M.; Vollmer, S. J., Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions, Ann. Appl. Probab., 24, 2455-2490 (2014) · Zbl 1307.65002
[28] Hamill, T. M.; Whitaker, J.; Snyder, C., Distance-dependent filtering of background covariance estimates in an ensemble Kalman filter, Mon. Weather Rev., 129, 2776-2790 (2001)
[29] Hodyss, D.; Bishop, C.; Morzfeld, M., To what extent is your data assimilation scheme designed to find the posterior mean, the posterior mode or something else? Tellus A: dynamic meteorology and oceanography, 68, 30625 (2016)
[30] Houtekamer, P.; Mitchell, H., A sequential ensemble Kalman filter for atmospheric data assimilation, Mon. Weather Rev., 129, 123-136 (2001)
[31] Houtekamer, P. L.; Mitchell, H. L.; Pellerin, G.; Buehner, M.; Charron, M.; Spacek, L.; Hansen, B., Atmospheric data assimilation with an ensemble Kalman filter: results with real observations, Mon. Weather Rev., 133, 604-620 (2005)
[32] Insua, D. R.; Ruggeri, F., Robust Bayesian Analysis, vol. 152 (2012), Springer Science & Business Media
[33] Kalos, M.; Whitlock, P., Monte Carlo Methods, vol. 1 (1986), John Wiley & Sons · Zbl 0655.65004
[34] Lee, Y.; Majda, A., State estimation and prediction using clustered particle filters, Proc. Natl. Acad. Sci. USA, 113, 14609-14614 (2016) · Zbl 1407.62341
[35] Lei, J.; Bickel, P., A moment matching ensemble filter for nonlinear non-Gaussian data assimilation, Mon. Weather Rev., 139, 3964-3973 (2011)
[36] Lindgren, F.; Rue, H.; Lindström, J., An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach, J. R. Stat. Soc., Ser. B, Stat. Methodol., 73, 423-498 (2011) · Zbl 1274.62360
[37] Lorenz, E. N., Predictability: a problem partly solved, (Proc. ECMWF Seminar on Predictability, vol. 1 (1996)), 1-18
[38] MacKay, D., Introduction to Monte Carlo methods, (Jordan, M. I., Learning in Graphical Models. Learning in Graphical Models, NATO Science Series (1998), Kluwer Academic Press), 175-204 · Zbl 0911.65004
[39] Martin, J.; Wilcox, L. C.; Burstedde, C.; Ghattas, O., A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM J. Sci. Comput., 34, A1460-A1487 (2012) · Zbl 1250.65011
[40] Morzfeld, M.; Hodyss, D.; Snyder, C., What the collapse of the ensemble Kalman filter tells us about particle filters, Tellus A, 69, Article 1283809 pp. (2017)
[41] Neal, R., MCMC using Hamiltonian dynamics, (Brooks, S.; Gelman, A.; Jones, G.; Meng, X.-L., Handbook of Markov Chain Monte Carlo (2011), Chapman & Hall: Chapman & Hall Oxford), ch. 5 · Zbl 1229.65018
[42] Norton, R.; Fox, C., Fast sampling in a linear-Gaussian inverse problem, SIAM/ASA J. Uncertain. Quantificat., 4, 1191-1218 (2016) · Zbl 1398.94081
[43] Owen, A., Monte Carlo Theory, Methods and Examples (2013)
[44] Penny, S.; Miyoshi, T., A local particle filter for high dimensional geophysical systems, Nonlinear Process. Geophys., 2, 1631-1658 (2015)
[45] Petra, N.; Martin, J.; Stadler, G.; Ghattas, O., A computational framework for infinite-dimensional Bayesian inverse problems. Part II: stochastic Newton MCMC with application to ice sheet flow inverse problems, SIAM J. Sci. Comput., 36, A1525-A1555 (2013) · Zbl 1303.35110
[46] Poterjoy, J., A localized particle filter for high-dimensional nonlinear systems, Mon. Weather Rev., 144, 59-76 (2015)
[47] Poterjoy, J.; Anderson, J., Efficient assimilation of simulated observations in a high-dimensional geophysical system using a localized particle filter, Mon. Weather Rev., 144, 2007-2020 (2016)
[48] Poterjoy, J.; Sobash, R.; Anderson, J., Convective-scale data assimilation for the weather research and forecasting model using the local particle filter, Mon. Weather Rev., 145, 1897-1918 (2017)
[49] Rebeschini, P.; van Handel, R., Can local particle filters beat the curse of dimensionality?, Ann. Appl. Probab., 25, 2809-2866 (2015) · Zbl 1325.60058
[50] Reich, S., A nonparametric ensemble transform method for Bayesian inference, Mon. Weather Rev., 35, 1337-1367 (2013) · Zbl 1362.65007
[51] Roberts, G.; Gelman, A.; Gilks, W., Weak convergence and optimal scaling of random walk Metropolis algorithms, Ann. Appl. Probab., 7, 110-120 (1997) · Zbl 0876.60015
[52] Roberts, G.; Rosenthal, J., Optimal scaling of discrete approximations to Langevin diffusions, J. R. Stat. Soc., Ser. B, Stat. Methodol., 60, 255-268 (1998) · Zbl 0913.60060
[53] Roberts, G. O.; Sahu, S. K., Updating schemes, correlation structure, blocking and parameterization for the Gibbs sampler, J. R. Stat. Soc., Ser. B, Stat. Methodol., 59, 291-317 (1997) · Zbl 0886.62083
[54] Rue, H.; Held, L., Gaussian Markov Random Fields: Theory and Applications (2005), CRC Press · Zbl 1093.60003
[55] Sakov, P.; Oliver, D. S.; Bertino, L., An iterative EnKF for strongly nonlinear systems, Mon. Weather Rev., 140, 1988-2004 (2012)
[56] Spantini, A.; Bigoni, D.; Marzouk, Y. M., Inference via low-dimensional couplings (2017)
[57] Spantini, A.; Solonen, A.; Cui, T.; Martin, J.; Tenorio, L.; Marzouk, Y. M., Optimal low-rank approximations of Bayesian linear inverse problems, SIAM J. Sci. Comput., 37, A2451-A2487 (2015) · Zbl 1325.62060
[58] Stuart, A., Inverse problems: a Bayesian perspective, Acta Numer., 19, 451-559 (2010) · Zbl 1242.65142
[59] Talagrand, O.; Courtier, P., Variational assimilation of meteorological observations with the adjoint vorticity equation. I: theory, Q. J. R. Meteorol. Soc., 113, 1311-1328 (1987)
[60] Tödter, J.; Ahrens, B., A second-order exact ensemble square root filter for nonlinear data assimilation, Mon. Weather Rev., 143, 1337-1367 (2015)
[61] Tong, X. T., Performance analysis of local ensemble Kalman filter (2019), Accepted by J. Nonlinear Science
[62] van Leeuwen, P.; Cheng, Y.; Reich, S., Nonlinear Data Assimilation (2015), Springer · Zbl 1330.62004
[63] Wolff, U., Monte Carlo errors with less errors, Comput. Phys. Commun., 156, 143-153 (2004) · Zbl 1196.65138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.