×

Goal-oriented optimal approximations of Bayesian linear inverse problems. (English) Zbl 1373.15027

Summary: We propose optimal dimensionality reduction techniques for the solution of goal-oriented linear-Gaussian inverse problems, where the quantity of interest (QoI) is a function of the inversion parameters. These approximations are suitable for large-scale applications. In particular, we study the approximation of the posterior covariance of the QoI as a low-rank negative update of its prior covariance and prove optimality of this update with respect to the natural geodesic distance on the manifold of symmetric positive definite matrices. Assuming exact knowledge of the posterior mean of the QoI, the optimality results extend to optimality in distribution with respect to the Kullback-Leibler divergence and the Hellinger distance between the associated distributions. We also propose the approximation of the posterior mean of the QoI as a low-rank linear function of the data and prove optimality of this approximation with respect to a weighted Bayes risk. Both of these optimal approximations avoid the explicit computation of the full posterior distribution of the parameters and instead focus on directions that are well informed by the data and relevant to the QoI. These directions stem from a balance among all the components of the goal-oriented inverse problem: prior information, forward model, measurement noise, and ultimate goals. We illustrate the theory using a high-dimensional inverse problem in heat transfer.

MSC:

15A29 Inverse problems in linear algebra
62F15 Bayesian inference
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. A. Absil, C. G. Baker, and K. A. Gallivan, {\it A truncated-CG style method for symmetric generalized eigenvalue problems}, J. Comput. Appl. Math, 189 (2006), pp. 274-285. · Zbl 1090.65042
[2] P. A. Absil, C. G. Baker, K. A. Gallivan, and A. Sameh, {\it Adaptive model trust region methods for generalized eigenvalue problems}, in International Conference on Computational Science, Springer, New York, 2005, pp. 33-41. · Zbl 1129.65307
[3] V. Akçelik, G. Biros, O. Ghattas, J. Hill, D. Keyes, and B. van Bloemen Waanders, {\it Parallel algorithms for PDE-constrained optimization}, Parallel Process. Sci. Comput., 20 (2006), p. 291.
[4] S. Amari and H. Nagaoka, {\it Methods of Information Geometry}, Transl. Math. Monogr. 191, AMS, Providence, RI, 2007. · Zbl 1146.62001
[5] V. Arsigny, P. Fillard, X. Pennec, and N. Ayache, {\it Geometric means in a novel vector space structure on symmetric positive-definite matrices}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 328-347. · Zbl 1144.47015
[6] C. Atkinson and A. F. S. Mitchell, {\it Rao’s distance measure}, Sankhyā A, 43 (1981), pp. 345-365. · Zbl 0534.62012
[7] H. Auvinen, J. M. Bardsley, H. Haario, and T. Kauranne, {\it Large-scale Kalman filtering using the limited memory BFGS method}, Electron. Trans. Numer. Anal., 35 (2009), pp. 217-233. · Zbl 1188.65084
[8] H. Auvinen, J. M. Bardsley, H. Haario, and T. Kauranne, {\it The variational Kalman filter and an efficient implementation using limited memory BFGS}, Internat. J. Numer. Methods Fluids, 64 (2010), pp. 314-335. · Zbl 1197.65213
[9] O. Axelsson and I. Kaporin, {\it On the sublinear and superlinear rate of convergence of conjugate gradient methods}, Numer. Algorithms, 25 (2000), pp. 1-22. · Zbl 0972.65024
[10] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, {\it Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide}, Software Environ. Tools 11, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[11] C. G. Baker, P. A. Absil, and K. A. Gallivan, {\it An implicit Riemannian trust-region method for the symmetric generalized eigenproblem}, in International Conference on Computational Science, Springer, New York, 2006, pp. 210-217. · Zbl 1155.65325
[12] A. Barachant, S. Bonnet, M. Congedo, and C. Jutten, {\it Classification of covariance matrices using a Riemannian-based kernel for BCI applications}, Neurocomputing, 112 (2013), pp. 172-178.
[13] T. L. Bergman, F. P. Incropera, and A. S. Lavine, {\it Fundamentals of Heat and Mass Transfer}, Wiley, New York, 2011.
[14] R. Bhatia, {\it Positive Definite Matrices}, Princeton University Press, Princeton, NJ, 2009. · Zbl 1125.15300
[15] R. Bhatia, {\it Matrix Analysis}, Grad. Texts in Math. 169, Springer Science & Business Media, New York, 2013.
[16] S. Bonnabel and R. Sepulchre, {\it Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1055-1070. · Zbl 1220.47025
[17] S. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[18] C. M. Branco, R. Ritchie, and V. Sklenicka, {\it Mechanical Behaviour of Materials at High Temperature}, NATO Sci. Partnership Subser. 15, Springer Science & Business Media, New York, 1996.
[19] T. Bui-Thanh, C. Burstedde, O. Ghattas, J. Martin, G. Stadler, and L. Wilcox, {\it Extreme-scale UQ for Bayesian inverse problems governed by PDEs}, in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, IEEE Computer Society Press, New York, 2012, p. 3.
[20] T. Bui-Thanh and O. Ghattas, {\it Analysis of the Hessian for inverse scattering problems:} I. {\it Inverse shape scattering of acoustic waves}, Inverse Problems, 28 (2012), 055001. · Zbl 1239.78006
[21] T. Bui-Thanh, O. Ghattas, and D. Higdon, {\it Adaptive Hessian-based nonstationary Gaussian process response surface method for probability density approximation with application to Bayesian solution of large-scale inverse problems}, SIAM J. Sci. Comput., 34 (2012), pp. A2837-A2871. · Zbl 1257.62035
[22] D. Calvetti and E. Somersalo, {\it Priorconditioners for linear systems}, Inverse Problems, 21 (2005), pp. 1397-1418. · Zbl 1087.65044
[23] S. T. Choi, {\it Iterative Methods for Singular Linear Equations and Least-Squares Problems}, Ph.D. thesis, Stanford University, 2006.
[24] E. Chow and Y. Saad, {\it Preconditioned Krylov subspace methods for sampling multivariate Gaussian distributions}, SIAM J. Sci. Comput., 36 (2014), pp. A588-A608. · Zbl 1296.60087
[25] J. Chung and M. Chung, {\it Computing optimal low-rank matrix approximations for image processing}, in Asilomar Conference on Signals, Systems and Computers, IEEE, 2013, pp. 670-674.
[26] J. Chung and M. Chung, {\it An efficient approach for computing optimal low-rank regularized inverse matrices}, Inverse Problems, 30 (2014), 114009. · Zbl 1305.65130
[27] J. Chung, M. Chung, and D. P. O’Leary, {\it Designing optimal spectral filters for inverse problems}, SIAM J. Sci. Comput., 33 (2011), pp. 3132-3152. · Zbl 1269.65040
[28] J. Chung, M. Chung, and D. P. O’Leary, {\it Optimal filters from calibration data for image deconvolution with data acquisition error}, J. Math. Imaging Vision, 44 (2012), pp. 366-374. · Zbl 1255.94011
[29] J. Chung, M. Chung, and D. P. O’Leary, {\it Optimal regularized low rank inverse approximation}, Linear Algebra Appl., 468 (2015), pp. 260-269. · Zbl 1307.65048
[30] T. Cui, K. J. H. Law, and Y. M. Marzouk, {\it Dimension-independent likelihood-informed MCMC}, J. Comput. Phys., 304 (2016), pp. 109-137. · Zbl 1349.65009
[31] T. Cui, J. Martin, Y. M. Marzouk, A. Solonen, and A. Spantini, {\it Likelihood-informed dimension reduction for nonlinear inverse problems}, Inverse Problems, 30 (2014), 114015. · Zbl 1310.62030
[32] J. Cullum and W. Donath, {\it A block Lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matrices}, in Conference on Decision and Control Including the 13th Symposium on Adaptive Processes, IEEE, 1974, pp. 505-509.
[33] M. Dashti and A. M. Stuart, {\it The Bayesian Approach to Inverse Problems}, preprint, , 2013.
[34] J. Dick, R. N. Gantner, Q. T. L. Gia, and C. Schwab, {\it Higher Order quasi-Monte Carlo Integration for Bayesian Estimation}, preprint, , 2016. · Zbl 1442.62051
[35] C. R. Dietrich and G. N. Newsam, {\it Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix}, SIAM J. Sci. Comput., 18 (1997), pp. 1088-1107. · Zbl 0890.65149
[36] M. P. do Carmo, {\it Riemannian Geometry}, Birkhäuser, Basel, 1992.
[37] L. Dykes and L. Reichel, {\it Simplified GSVD computations for the solution of linear discrete ill-posed problems}, J. Comput. Appl. Math., 255 (2014), pp. 15-27. · Zbl 1291.65117
[38] R. A. Fisher, {\it On the mathematical foundations of theoretical statistics}, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 222 (1922), pp. 309-368. · JFM 48.1280.02
[39] H. P. Flath, L. Wilcox, V. Akçelik, J. Hill, B. van Bloemen Waanders, and O. Ghattas, {\it 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), pp. 407-432. · Zbl 1229.65174
[40] P. T. Fletcher, C. Lu, S. M. Pizer, and S. Joshi, {\it Principal geodesic analysis for the study of nonlinear statistics of shape}, IEEE Trans. Medical Imaging, 23 (2004), pp. 995-1005.
[41] D. C. Fong and M. Saunders, {\it LSMR: An iterative algorithm for sparse least-squares problems}, SIAM J. Sci. Comput., 33 (2011), pp. 2950-2971. · Zbl 1232.65052
[42] W. Förstner and B. Moonen, {\it A metric for covariance matrices}, in Geodesy–The Challenge of the 3rd Millennium, Springer, New York, 2003, pp. 299-309.
[43] C. Fox and A. Parker, {\it Convergence in variance of Chebyshev accelerated Gibbs samplers}, SIAM J. Sci. Comput., 36 (2014), pp. A124-A147. · Zbl 1291.65097
[44] S. Friedland and A. Torokhti, {\it Generalized rank-constrained matrix approximations}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 656-659. · Zbl 1144.15004
[45] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 3rd ed., Johns Hopkins University Press, Baltimore, 2012. · Zbl 1268.65037
[46] G. H. Golub and Q. Ye, {\it An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems}, SIAM J. Sci. Comput., 24 (2002), pp. 312-334. · Zbl 1016.65017
[47] G. Guglielmini and C. Pisoni, {\it Elementi di trasmissione del calore}, Veschi, 1990.
[48] N. Halko, P. Martinsson, and J. A. Tropp, {\it Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions}, SIAM Rev., 53 (2011), pp. 217-288. · Zbl 1269.65043
[49] P. C. Hansen, {\it Regularization, GSVD and truncated GSVD}, BIT, 29 (1989), pp. 491-504.
[50] M. R. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. Natl. Bur. Standards, 49 DC, (1952), pp. 409-436. · Zbl 0048.09901
[51] D. Higdon, C. S. Reese, J. D. Moulton, J. A. Vrugt, and C. Fox, {\it Posterior exploration for computationally intensive forward models}, in Handbook of Markov Chain Monte Carlo, CRC Press, Boca Raton, FL, 2011, pp. 401-418. · Zbl 1229.65016
[52] I. Horev, F. Yger, and M. Sugiyama, {\it Geometry-aware principal component analysis for symmetric positive definite matrices}, in JMLR: Workshop and Conference Proceedings, 2015. · Zbl 1459.62236
[53] Y. Hua and W. Liu, {\it Generalized Karhunen-Loeve transform}, IEEE Signal Process. Lett., 5 (1998), pp. 141-142.
[54] T. Isaac, N. Petra, G. Stadler, and O. Ghattas, {\it Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the antarctic ice sheet}, J. Comput. Phys., 296 (2015), pp. 348-368. · Zbl 1352.86017
[55] S. T. Jensen, {\it private communication}, 1976.
[56] J. Kaipio and E. Somersalo, {\it Statistical inverse problems: Discretization, model reduction and inverse crimes}, J. Comput. Appl. Math., 198 (2007), pp. 493-504. · Zbl 1101.65008
[57] A. G. Kalmikov and P. Heimbach, {\it A Hessian-based method for uncertainty quantification in global ocean state estimation}, SIAM J. Sci. Comput., 36 (2014), pp. S267-S295. · Zbl 1311.35321
[58] A. Klinvex, F. Saied, and A. Sameh, {\it Parallel implementations of the trace minimization scheme tracemin for the sparse symmetric eigenvalue problem}, Comput. Math. Appl., 65 (2013), pp. 460-468. · Zbl 1319.65027
[59] D. Kressner, M. M. Pandur, and M. Shao, {\it An indefinite variant of LOBPCG for definite matrix pencils}, Numer. Algorithms, 66 (2014), pp. 681-703. · Zbl 1297.65040
[60] C. Lanczos, {\it An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators}, U.S. Government Publishing Office, 1950. · Zbl 0045.39702
[61] W. Li and O. A. Cirpka, {\it Efficient geostatistical inverse methods for structured and unstructured grids}, Water Resources Res., 42 (2006).
[62] E. Liberty, F. Woolfe, P. Martinsson, V. Rokhlin, and M. Tygert, {\it Randomized algorithms for the low-rank approximation of matrices}, Proc. Natl. Acad. Sci., USA, 104 (2007), pp. 20167-20172. · Zbl 1215.65080
[63] C. Lieberman and K. Willcox, {\it Goal-oriented inference: Approach, linear theory, and application to advection diffusion}, SIAM J. Sci. Comput., 34 (2012), pp. A1880-A1904. · Zbl 1250.62058
[64] C. Lieberman and K. Willcox, {\it Nonlinear goal-oriented Bayesian inference: Application to carbon capture and storage}, SIAM J. Sci. Comput., 36 (2014), pp. B427-B449. · Zbl 1429.62711
[65] J. Liesen and P. Tichỳ, {\it Convergence analysis of Krylov subspace methods}, GAMM-Mitt., 27 (2004), pp. 153-173. · Zbl 1071.65041
[66] F. Lindgren, H. Rue, and J. Lindström, {\it An explicit link between Gaussian fields and Gaussian Markov random fields: The stochastic partial differential equation approach}, J. Roy. Statist. Soc. Ser. B, 73 (2011), pp. 423-498. · Zbl 1274.62360
[67] P. C. Mahalanobis, {\it On the generalized distance in statistics}, Proc. Natl. Inst. Sci. (Calcutta), 2 (1936), pp. 49-55. · Zbl 0015.03302
[68] I. Markovsky, {\it Structured low-rank approximation and its applications}, Automatica, 44 (2008), pp. 891-909. · Zbl 1283.93061
[69] J. Martin, L. Wilcox, C. Burstedde, and O. Ghattas, {\it A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion}, SIAM J. Sci. Comput., 34 (2012), pp. A1460-A1487. · Zbl 1250.65011
[70] Y. M. Marzouk and H. N. Najm, {\it Dimensionality reduction and polynomial chaos acceleration of Bayesian inference in inverse problems}, J. Comput. Phys., 228 (2009), pp. 1862-1902. · Zbl 1161.65308
[71] X. Meng, M. A. Saunders, and M. W. Mahoney, {\it LSRN: A parallel iterative solver for strongly over-or underdetermined systems}, SIAM J. Sci. Comput., 36 (2014), pp. C95-C118. · Zbl 1298.65053
[72] M. Moakher and M. Zéraï, {\it The Riemannian geometry of the space of positive-definite matrices and its application to the regularization of positive-definite matrix-valued data}, J. Math. Imaging Vis., 40 (2011), pp. 171-187. · Zbl 1255.68195
[73] T. Moselhy and Y. Marzouk, {\it Bayesian inference with optimal maps}, J. Comput. Phys., 231 (2012), pp. 7815-7850. · Zbl 1318.62087
[74] J. B. Nagel and B. Sudret, {\it Spectral likelihood expansions for Bayesian inference}, J. Comput. Phys., 309 (2016), pp. 267-294. · Zbl 1351.62077
[75] D. P. O’Leary, {\it The block conjugate gradient algorithm and related methods}, Linear Algebra Appl., 29 (1980), pp. 293-322. · Zbl 0426.65011
[76] C. C. Paige, {\it Computational variants of the Lanczos method for the eigenproblem}, IMA J. Appl. Math., 10 (1972), pp. 373-381. · Zbl 0253.65020
[77] C. C. Paige and M. A. Saunders, {\it Towards a generalized singular value decomposition}, SIAM J. Numer. Anal., 18 (1981), pp. 398-405. · Zbl 0471.65018
[78] C. C. Paige and M. A. Saunders, {\it LSQR: An algorithm for sparse linear equations and sparse least squares}, ACM Trans. Math. Software, 8 (1982), pp. 43-71. · Zbl 0478.65016
[79] L. Pardo, {\it Statistical Inference Based on Divergence Measures}, CRC Press, Boca Raton, FL, 2005. · Zbl 1118.62008
[80] A. Parker and C. Fox, {\it Sampling Gaussian distributions in Krylov spaces with conjugate gradients}, SIAM J. Sci. Comput., 34 (2012), pp. B312-B334. · Zbl 1246.65057
[81] X. Pennec, P. Fillard, and N. Ayache, {\it A Riemannian framework for tensor computing}, Int. J. Comput. Vis., 66 (2006), pp. 41-66. · Zbl 1287.53031
[82] N. Petra, J. Martin, G. Stadler, and O. Ghattas, {\it 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 (2014), pp. A1525-A1555. · Zbl 1303.35110
[83] A. Quarteroni and A. Valli, {\it Numerical Approximation of Partial Differential Equations}, Springer Ser. Comput. Math. 23, Springer Science & Business Media, New York, 2008. · Zbl 1151.65339
[84] C. R. Rao, {\it Information and the accuracy attainable in the estimation of statistical parameters}, Bull. Calcutta Math. Soc., 37 (1945), pp. 81-89. · Zbl 0063.06420
[85] C. R. Rao, {\it On the distance between two populations}, Sankhya, 9 (1949), pp. 246-248.
[86] C. R. Rao, {\it Differential metrics in probability spaces}, Differential Geom. Statist. Inference, 10 (1987), pp. 217-240.
[87] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, SIAM, Philadelphia, 2003. · Zbl 1031.65046
[88] A. K. Saibaba, J. Lee, and P. K. Kitanidis, {\it Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen-Loève expansion}, Numer. Linear Algebra Appl., (2015). · Zbl 1413.65104
[89] A. H. Sameh and J. A. Wisniewski, {\it A trace minimization algorithm for the generalized eigenvalue problem}, SIAM J. Numer. Anal., 19 (1982), pp. 1243-1259. · Zbl 0493.65017
[90] C. Schillings and C. Schwab, {\it Sparse, adaptive Smolyak quadratures for Bayesian inverse problems}, Inverse Problems, 29 (2013), 065011. · Zbl 1278.65008
[91] C. Schillings and C. Schwab, {\it Scaling Limits in Computational Bayesian Inversion}, Research Report 2014-26, ETH Zürich, 2014. · Zbl 1358.65013
[92] M. K. Schneider and A. S. Willsky, {\it A Krylov subspace method for covariance approximation and simulation of random processes and fields}, Multidimens. Syst. Signal Process., 14 (2003), pp. 295-318. · Zbl 1056.93020
[93] L. T. Skovgaard, {\it A Riemannian geometry of the multivariate normal model}, Scand. J. Stat., 11 (1984), pp. 211-223. · Zbl 0579.62033
[94] S. T. Smith, {\it Covariance, subspace, and intrinsic Cramér-Rao bounds}, IEEE Trans. Signal Process., 53 (2005), pp. 1610-1630. · Zbl 1370.94242
[95] A. Solonen, H. Haario, J. Hakkarainen, H. Auvinen, I. Amour, and T. Kauranne, {\it Variational ensemble Kalman filtering using limited memory BFGS}, Electron. Trans. Numer. Anal., 39 (2012), pp. 271-285. · Zbl 1321.93060
[96] S. Sommer, F. Lauze, S. Hauberg, and M. Nielsen, {\it Manifold valued statistics, exact principal geodesic analysis and the effect of linear approximations}, in Proceedings of Computer Vision–ECCV 2010, Springer, 2010, pp. 43-56.
[97] A. Spantini, A. Solonen, T. Cui, J. Martin, L. Tenorio, and Y. Marzouk, {\it Optimal low-rank approximations of Bayesian linear inverse problems}, SIAM J. Sci. Comput., 37 (2015), pp. A2451-A2487. · Zbl 1325.62060
[98] A. M. Stuart, {\it Inverse problems: a Bayesian perspective}, Acta Numer., 19 (2010), pp. 451-559. · Zbl 1242.65142
[99] C. F. Van Loan, {\it Generalizing the singular value decomposition}, SIAM J. Numer. Anal., 13 (1976), pp. 76-83. · Zbl 0338.65022
[100] A. T. A. Wood and G. Chan, {\it Simulation of stationary Gaussian processes in \([0, 1]^d\)}, J. Comput. Graph. Statist., 3 (1994), pp. 409-432.
[101] Y. Yue and P. L. Speckman, {\it Nonstationary spatial Gaussian Markov random fields}, J. Comput. Graph. Statist., 19 (2010), pp. 96-116.
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.