Certified dimension reduction in nonlinear Bayesian inverse problems

Zahm, Olivier; Cui, Tiangang; Law, Kody; Spantini, Alessio; Marzouk, Youssef

doi:10.1090/mcom/3737

Certified dimension reduction in nonlinear Bayesian inverse problems
HTML articles powered by AMS MathViewer

by Olivier Zahm, Tiangang Cui, Kody Law, Alessio Spantini and Youssef Marzouk HTML | PDF

Math. Comp. 91 (2022), 1789-1835 Request permission

Abstract:

We propose a dimension reduction technique for Bayesian inverse problems with nonlinear forward operators, non-Gaussian priors, and non-Gaussian observation noise. The likelihood function is approximated by a ridge function, i.e., a map which depends nontrivially only on a few linear combinations of the parameters. We build this ridge approximation by minimizing an upper bound on the Kullback–Leibler divergence between the posterior distribution and its approximation. This bound, obtained via logarithmic Sobolev inequalities, allows one to certify the error of the posterior approximation. Computing the bound requires computing the second moment matrix of the gradient of the log-likelihood function. In practice, a sample-based approximation of the upper bound is then required. We provide an analysis that enables control of the posterior approximation error due to this sampling. Numerical and theoretical comparisons with existing methods illustrate the benefits of the proposed methodology.

References

S. Agapiou, O. Papaspiliopoulos, D. Sanz-Alonso, and A. M. Stuart, Importance sampling: intrinsic dimension and computational cost, Statist. Sci. 32 (2017), no. 3, 405–431. MR 3696003, DOI 10.1214/17-STS611
Yves F. Atchadé, An adaptive version for the Metropolis adjusted Langevin algorithm with a truncated drift, Methodol. Comput. Appl. Probab. 8 (2006), no. 2, 235–254. MR 2324873, DOI 10.1007/s11009-006-8550-0
D. Bakry and Michel Émery, Diffusions hypercontractives, Séminaire de probabilités, XIX, 1983/84, Lecture Notes in Math., vol. 1123, Springer, Berlin, 1985, pp. 177–206 (French). MR 889476, DOI 10.1007/BFb0075847
Dominique Bakry, Ivan Gentil, and Michel Ledoux, Analysis and geometry of Markov diffusion operators, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 348, Springer, Cham, 2014. MR 3155209, DOI 10.1007/978-3-319-00227-9
Arindam Banerjee, Xin Guo, and Hui Wang, On the optimality of conditional expectation as a Bregman predictor, IEEE Trans. Inform. Theory 51 (2005), no. 7, 2664–2669. MR 2246384, DOI 10.1109/TIT.2005.850145
Alexandros Beskos, Ajay Jasra, Kody Law, Youssef Marzouk, and Yan Zhou, Multilevel sequential Monte Carlo with dimension-independent likelihood-informed proposals, SIAM/ASA J. Uncertain. Quantif. 6 (2018), no. 2, 762–786. MR 3810512, DOI 10.1137/17M1120993
G. Blanchard, O. Bousquet, and L. Zwald, Statistical properties of kernel principal component analysis, Mach. Learn. 66 (2007), no. 2–3, 259–294.
S. G. Bobkov and M. Ledoux, From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities, Geom. Funct. Anal. 10 (2000), no. 5, 1028–1052. MR 1800062, DOI 10.1007/PL00001645
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities, Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence; With a foreword by Michel Ledoux. MR 3185193, DOI 10.1093/acprof:oso/9780199535255.001.0001
M. Brennan, D. Bigoni, O. Zahm, A. Spantini, and Y. Marzouk, Greedy inference with structure-exploiting lazy maps, Adv. Neural Inform. Process. Syst. 33 (2020).
Yuxin Chen, David Keyes, Kody J. H. Law, and Hatem Ltaief, Accelerated dimension-independent adaptive Metropolis, SIAM J. Sci. Comput. 38 (2016), no. 5, S539–S565. MR 3565576, DOI 10.1137/15M1026432
J. Andrés Christen and Colin Fox, Markov chain Monte Carlo using an approximation, J. Comput. Graph. Statist. 14 (2005), no. 4, 795–810. MR 2211367, DOI 10.1198/106186005X76983
Albert Cohen, Ingrid Daubechies, Ronald DeVore, Gerard Kerkyacharian, and Dominique Picard, Capturing ridge functions in high dimensions from point queries, Constr. Approx. 35 (2012), no. 2, 225–243. MR 2891227, DOI 10.1007/s00365-011-9147-6
Patrick R. Conrad, Youssef M. Marzouk, Natesh S. Pillai, and Aaron Smith, Accelerating asymptotically exact MCMC for computationally intensive models via local approximations, J. Amer. Statist. Assoc. 111 (2016), no. 516, 1591–1607. MR 3601720, DOI 10.1080/01621459.2015.1096787
Paul G. Constantine, Eric Dow, and Qiqi Wang, Active subspace methods in theory and practice: applications to kriging surfaces, SIAM J. Sci. Comput. 36 (2014), no. 4, A1500–A1524. MR 3233940, DOI 10.1137/130916138
Paul G. Constantine, Carson Kent, and Tan Bui-Thanh, Accelerating Markov chain Monte Carlo with active subspaces, SIAM J. Sci. Comput. 38 (2016), no. 5, A2779–A2805. MR 3543164, DOI 10.1137/15M1042127
T. Cui, C. Fox, and M. O’Sullivan, Bayesian calibration of a large-scale geothermal reservoir model by a new adaptive delayed acceptance Metropolis Hastings algorithm, Water Resour. Res. 47 (2011), no. 10, W10521.
Tiangang Cui, Colin Fox, and Michael J. O’Sullivan, A posteriori stochastic correction of reduced models in delayed-acceptance MCMC, with application to multiphase subsurface inverse problems, Internat. J. Numer. Methods Engrg. 118 (2019), no. 10, 578–605. MR 3942044, DOI 10.1002/nme.6028
T. Cui, S. Dolgov, and O. Zahm, Conditional deep inverse Rosenblatt transports, Preprint, arXiv:2106.04170, 2021.
Tiangang Cui, Kody J. H. Law, and Youssef M. Marzouk, Dimension-independent likelihood-informed MCMC, J. Comput. Phys. 304 (2016), 109–137. MR 3422405, DOI 10.1016/j.jcp.2015.10.008
T. Cui, J. Martin, Y. M. Marzouk, A. Solonen, and A. Spantini, Likelihood-informed dimension reduction for nonlinear inverse problems, Inverse Problems 30 (2014), no. 11, 114015, 28. MR 3274599, DOI 10.1088/0266-5611/30/11/114015
Tiangang Cui, Youssef Marzouk, and Karen Willcox, Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction, J. Comput. Phys. 315 (2016), 363–387. MR 3490388, DOI 10.1016/j.jcp.2016.03.055
Tiangang Cui, Youssef M. Marzouk, and Karen E. Willcox, Data-driven model reduction for the Bayesian solution of inverse problems, Internat. J. Numer. Methods Engrg. 102 (2015), no. 5, 966–990. MR 3341244, DOI 10.1002/nme.4748
Tiangang Cui and Olivier Zahm, Data-free likelihood-informed dimension reduction of Bayesian inverse problems, Inverse Problems 37 (2021), no. 4, Paper No. 045009, 41. MR 4234453, DOI 10.1088/1361-6420/abeafb
Pierre Del Moral, Arnaud Doucet, and Ajay Jasra, Sequential Monte Carlo samplers, J. R. Stat. Soc. Ser. B Stat. Methodol. 68 (2006), no. 3, 411–436. MR 2278333, DOI 10.1111/j.1467-9868.2006.00553.x
Simon Duane, A. D. Kennedy, Brian J. Pendleton, and Duncan Roweth, Hybrid Monte Carlo, Phys. Lett. B 195 (1987), no. 2, 216–222. MR 3960671, DOI 10.1016/0370-2693(87)91197-x
H. P. Flath, L. C. Wilcox, V. Akçelik, J. Hill, B. van Bloemen Waanders, and O. Ghattas, Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations, SIAM J. Sci. Comput. 33 (2011), no. 1, 407–432. MR 2783201, DOI 10.1137/090780717
Massimo Fornasier, Karin Schnass, and Jan Vybiral, Learning functions of few arbitrary linear parameters in high dimensions, Found. Comput. Math. 12 (2012), no. 2, 229–262. MR 2898783, DOI 10.1007/s10208-012-9115-y
Mark Girolami and Ben Calderhead, Riemann manifold Langevin and Hamiltonian Monte Carlo methods, J. R. Stat. Soc. Ser. B Stat. Methodol. 73 (2011), no. 2, 123–214. With discussion and a reply by the authors. MR 2814492, DOI 10.1111/j.1467-9868.2010.00765.x
N. Gozlan, C. Roberto, and P.-M. Samson, Characterization of Talagrand’s transport-entropy inequalities in metric spaces, Ann. Probab. 41 (2013), no. 5, 3112–3139. MR 3127876, DOI 10.1214/12-AOP757
Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. MR 420249, DOI 10.2307/2373688
A. Guionnet and B. Zegarlinski, Lectures on logarithmic Sobolev inequalities, Séminaire de Probabilités, XXXVI, Lecture Notes in Math., vol. 1801, Springer, Berlin, 2003, pp. 1–134. MR 1971582, DOI 10.1007/978-3-540-36107-7_{1}
H. Haario, M. Laine, M. Lehtinen, E. Saksman, and J. Tamminen, Markov chain Monte Carlo methods for high dimensional inversion in remote sensing, J. R. Stat. Soc. Ser. B Stat. Methodol. 66 (2004), no. 3, 591–607. MR 2088292, DOI 10.1111/j.1467-9868.2004.02053.x
Heikki Haario, Eero Saksman, and Johanna Tamminen, An adaptive metropolis algorithm, Bernoulli 7 (2001), no. 2, 223–242. MR 1828504, DOI 10.2307/3318737
Matthew D. Hoffman and Andrew Gelman, The no-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo, J. Mach. Learn. Res. 15 (2014), 1593–1623. MR 3214779
Richard Holley and Daniel Stroock, Logarithmic Sobolev inequalities and stochastic Ising models, J. Statist. Phys. 46 (1987), no. 5-6, 1159–1194. MR 893137, DOI 10.1007/BF01011161
Heinrich Jung, Ueber die kleinste Kugel, die eine räumliche Figur einschliesst, J. Reine Angew. Math. 123 (1901), 241–257 (German). MR 1580570, DOI 10.1515/crll.1901.123.241
Jari Kaipio and Erkki Somersalo, Statistical and computational inverse problems, Applied Mathematical Sciences, vol. 160, Springer-Verlag, New York, 2005. MR 2102218
Olav Kallenberg, Foundations of modern probability, Probability and its Applications (New York), Springer-Verlag, New York, 1997. MR 1464694
E. Kokiopoulou, J. Chen, and Y. Saad, Trace optimization and eigenproblems in dimension reduction methods, Numer. Linear Algebra Appl. 18 (2011), no. 3, 565–602. MR 2760068, DOI 10.1002/nla.743
Solomon Kullback, Information theory and statistics, Dover Publications, Inc., Mineola, NY, 1997. Reprint of the second (1968) edition. MR 1461541
Otto Lamminpää, Marko Laine, Simo Tukiainen, and Johanna Tamminen, Likelihood informed dimension reduction for remote sensing of atmospheric constituent profiles, 2017 MATRIX annals, MATRIX Book Ser., vol. 2, Springer, Cham, 2019, pp. 65–78. MR 3931599
Michel Ledoux, Concentration of measure and logarithmic Sobolev inequalities, Séminaire de Probabilités, XXXIII, Lecture Notes in Math., vol. 1709, Springer, Berlin, 1999, pp. 120–216. MR 1767995, DOI 10.1007/BFb0096511
Jinglai Li, A note on the Karhunen-Loève expansions for infinite-dimensional Bayesian inverse problems, Statist. Probab. Lett. 106 (2015), 1–4. MR 3389963, DOI 10.1016/j.spl.2015.06.025
W. Li and O. A. Cirpka, Efficient geostatistical inverse methods for structured and unstructured grids, Water Resour. Res. 42 (2006), no. 6.
Chad Lieberman, Karen Willcox, and Omar Ghattas, Parameter and state model reduction for large-scale statistical inverse problems, SIAM J. Sci. Comput. 32 (2010), no. 5, 2523–2542. MR 2684726, DOI 10.1137/090775622
Finn Lindgren, Håvard Rue, and Johan Lindström, 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 (2011), no. 4, 423–498. With discussion and a reply by the authors. MR 2853727, DOI 10.1111/j.1467-9868.2011.00777.x
A. Manzoni, S. Pagani, and T. Lassila, Accurate solution of Bayesian inverse uncertainty quantification problems combining reduced basis methods and reduction error models, SIAM/ASA J. Uncertain. Quantif. 4 (2016), no. 1, 380–412. MR 3488168, DOI 10.1137/140995817
Youssef M. Marzouk and Habib N. Najm, Dimensionality reduction and polynomial chaos acceleration of Bayesian inference in inverse problems, J. Comput. Phys. 228 (2009), no. 6, 1862–1902. MR 2500666, DOI 10.1016/j.jcp.2008.11.024
Radford M. Neal, MCMC using Hamiltonian dynamics, Handbook of Markov chain Monte Carlo, Chapman & Hall/CRC Handb. Mod. Stat. Methods, CRC Press, Boca Raton, FL, 2011, pp. 113–162. MR 2858447
F. Otto and C. Villani, Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality, J. Funct. Anal. 173 (2000), no. 2, 361–400. MR 1760620, DOI 10.1006/jfan.1999.3557
A. B. Owen, Monte Carlo Theory, Methods and Examples, 2013. Available at https://artowen.su.domains/mc/.
Allan Pinkus, Ridge functions, Cambridge Tracts in Mathematics, vol. 205, Cambridge University Press, Cambridge, 2015. MR 3559591, DOI 10.1017/CBO9781316408124
Markus Reiss and Martin Wahl, Nonasymptotic upper bounds for the reconstruction error of PCA, Ann. Statist. 48 (2020), no. 2, 1098–1123. MR 4102689, DOI 10.1214/19-AOS1839
Christian P. Robert and George Casella, Monte Carlo statistical methods, Springer Texts in Statistics, Springer-Verlag, New York, 1999. MR 1707311, DOI 10.1007/978-1-4757-3071-5
O. S. Rothaus, Lower bounds for eigenvalues of regular Sturm-Liouville operators and the logarithmic Sobolev inequality, Duke Math. J. 45 (1978), no. 2, 351–362. MR 481241, DOI 10.1215/S0012-7094-78-04518-0
Paul-Baptiste Rubio, François Louf, and Ludovic Chamoin, Fast model updating coupling Bayesian inference and PGD model reduction, Comput. Mech. 62 (2018), no. 6, 1485–1509. MR 3877568, DOI 10.1007/s00466-018-1575-8
Trent Michael Russi, Uncertainty quantification with experimental data and complex system models, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–University of California, Berkeley. MR 2941538
Claudia Schillings, Björn Sprungk, and Philipp Wacker, On the convergence of the Laplace approximation and noise-level-robustness of Laplace-based Monte Carlo methods for Bayesian inverse problems, Numer. Math. 145 (2020), no. 4, 915–971. MR 4125981, DOI 10.1007/s00211-020-01131-1
Alessio Spantini, Antti Solonen, Tiangang Cui, James Martin, Luis Tenorio, and Youssef Marzouk, Optimal low-rank approximations of Bayesian linear inverse problems, SIAM J. Sci. Comput. 37 (2015), no. 6, A2451–A2487. MR 3418226, DOI 10.1137/140977308
A. M. Stuart, Inverse problems: a Bayesian perspective, Acta Numer. 19 (2010), 451–559. MR 2652785, DOI 10.1017/S0962492910000061
J. Tamminen, Adaptive Markov chain Monte Carlo algorithms with geophysical applications, Ph.D. Thesis, University of Helsinki, Faculty of Science, Department of Mathematics, 2004.
Hemant Tyagi and Volkan Cevher, Learning non-parametric basis independent models from point queries via low-rank methods, Appl. Comput. Harmon. Anal. 37 (2014), no. 3, 389–412. MR 3256780, DOI 10.1016/j.acha.2014.01.002
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170
Olivier Zahm, Paul G. Constantine, Clémentine Prieur, and Youssef M. Marzouk, Gradient-based dimension reduction of multivariate vector-valued functions, SIAM J. Sci. Comput. 42 (2020), no. 1, A534–A558. MR 4069329, DOI 10.1137/18M1221837