A Bayesian conjugate gradient method (with discussion). (English) Zbl 1430.62024

Summary: A fundamental task in numerical computation is the solution of large linear systems. The conjugate gradient method is an iterative method which offers rapid convergence to the solution, particularly when an effective preconditioner is employed. However, for more challenging systems a substantial error can be present even after many iterations have been performed. The estimates obtained in this case are of little value unless further information can be provided about, for example, the magnitude of the error. In this paper we propose a novel statistical model for this error, set in a Bayesian framework. Our approach is a strict generalisation of the conjugate gradient method, which is recovered as the posterior mean for a particular choice of prior. The estimates obtained are analysed with Krylov subspace methods and a contraction result for the posterior is presented. The method is then analysed in a simulation study as well as being applied to a challenging problem in medical imaging.


62C10 Bayesian problems; characterization of Bayes procedures
62F15 Bayesian inference
65F10 Iterative numerical methods for linear systems
Full Text: DOI arXiv Euclid


[1] Ajiz, M. A. and Jennings, A. (1984). “A robust incomplete Choleski-conjugate gradient algorithm.” International Journal for Numerical Methods in Engineering, 20(5): 949-966. · Zbl 0541.65019 · doi:10.1002/nme.1620200511
[2] Allaire, G. and Kaber, S. M. (2008). Numerical Linear Algebra, volume 55 of Texts in Applied Mathematics. Springer New York. · Zbl 1135.65014
[3] Bartels, S. and Hennig, P. (2016). “Probabilistic Approximate Least-Squares.” In Proceedings of Artificial Intelligence and Statistics (AISTATS).
[4] Benzi, M. (2002). “Preconditioning Techniques for Large Linear Systems: A Survey.” Journal of Computational Physics, 182(2): 418-477. · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[5] Besag, J. and Green, P. J. (1993). “Spatial statistics and Bayesian computation.” Journal of the Royal Statistical Society. Series B (Statistical Methodology), 25-37. · Zbl 0800.62572 · doi:10.1111/j.2517-6161.1993.tb01467.x
[6] Bogachev, V. I. (1998). Gaussian Measures, volume 62. American Mathematical Society Providence. · Zbl 0913.60035
[7] Bramble, J. H., Pasciak, J. E., and Xu, J. (1990). “Parallel Multilevel Preconditioners.” Mathematics of Computation, 55(191): 1-22. · Zbl 0703.65076 · doi:10.1090/S0025-5718-1990-1023042-6
[8] Briol, F.-X., Oates, C. J., Girolami, M., Osborne, M. A., and Sejdinovic, D. (2018). “Probabilistic Integration: A Role in Statistical Computation?” arXiv:1512.00933. · Zbl 1420.62135
[9] Calvetti, D., Pitolli, F., Somersalo, E., and Vantaggi, B. (2018). “Bayes Meets Krylov: Statistically Inspired Preconditioners for CGLS.” SIAM Review, 60(2): 429-461. · Zbl 1392.65047 · doi:10.1137/15M1055061
[10] Cheng, K.-S., Isaacson, D., Newell, J. C., and Gisser, D. G. (1989). “Electrode models for electric current computed tomography.” IEEE Transactions on Biomedical Engineering, 36(9): 918-924.
[11] Cockayne, J., Oates, C. J., Ipsen, I. C. F., and Girolami, M. (2019). “Supplementary Material for “Bayesian Conjugate-Gradient Method”.” Bayesian Analysis. · Zbl 1430.62024
[12] Cockayne, J., Oates, C., Sullivan, T., and Girolami, M. (2017). “Bayesian Probabilistic Numerical Methods.” arXiv:1702.03673. · Zbl 1451.65179
[13] Cockayne, J., Oates, C., Sullivan, T. J., and Girolami, M. (2016). “Probabilistic Meshless Methods for Partial Differential Equations and Bayesian Inverse Problems.” arXiv:1605.07811v1.
[14] Cotter, S. L., Roberts, G. O., Stuart, A. M., and White, D. (2013). “MCMC methods for functions: Modifying old algorithms to make them faster.” Statistical Science, 28(3): 424-446. · Zbl 1331.62132 · doi:10.1214/13-STS421
[15] Davis, T. A. (2006). Direct Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 1119.65021
[16] Diaconis, P. (1988). “Bayesian numerical analysis.” Statistical Decision Theory and Related Topics IV, 1: 163-175. · Zbl 0671.65117
[17] Dunlop, M. M. and Stuart, A. M. (2016). “The Bayesian formulation of EIT: Analysis and algorithms.” Inverse Problems and Imaging, 10: 1007-1036. · Zbl 1348.62104 · doi:10.3934/ipi.2016030
[18] Evans, L. (2010). Partial Differential Equations, volume 19 of Graduate Studies in Mathematics. Providence, Rhode Island: American Mathematical Society, second edition. · Zbl 1194.35001
[19] Fasshauer, G. E. (1999). “Solving differential equations with radial basis functions: Multilevel methods and smoothing.” Advances in Computational Mathematics, 11(2-3): 139-159. · Zbl 0940.65122 · doi:10.1023/A:1018919824891
[20] Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., and Rubin, D. B. (2014). Bayesian Data Analysis, volume 2. CRC press Boca Raton, FL. · Zbl 1279.62004
[21] Golub, G. H. and Van Loan, C. F. (2013). Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition. · Zbl 1268.65037
[22] Hennig, P. (2015). “Probabilistic Interpretation of Linear Solvers.” SIAM Journal on Optimization, 25(1): 234-260. · Zbl 1356.49042 · doi:10.1137/140955501
[23] Hennig, P., Osborne, M. A., and Girolami, M. (2015). “Probabilistic numerics and uncertainty in computations.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science, 471(2179): 20150142. · Zbl 1372.65010 · doi:10.1098/rspa.2015.0142
[24] Hestenes, M. R. and Stiefel, E. (1952). “Methods of conjugate gradients for solving linear systems.” Journal of Research of the National Bureau of Standards, 49(6): 409. · Zbl 0048.09901 · doi:10.6028/jres.049.044
[25] Holder, D. S. (2004). Electrical Impedance Tomography: Methods, History and Applications. CRC Press.
[26] Isaacson, D., Mueller, J. L., Newell, J. C., and Siltanen, S. (2004). “Reconstructions of chest phantoms by the D-bar method for electrical impedance tomography.” IEEE Transactions on Medical Imaging, 23(7): 821-828.
[27] Larkin, F. M. (1972). “Gaussian measure in Hilbert space and applications in numerical analysis.” The Rocky Mountain Journal of Mathematics, 2(3): 379-421. · Zbl 0258.65058 · doi:10.1216/RMJ-1972-2-3-379
[28] Liesen, J. and Strakos, Z. (2012). Krylov Subspace Methods. Principles and Analysis. Oxford University Press. · Zbl 1263.65034
[29] Oates, C. J., Cockayne, J., Aykroyd, R. G., and Girolami, M. (2019). “Bayesian Probabilistic Numerical Methods in Time-Dependent State Estimation for Industrial Hydrocyclone Equipment.” Journal of the American Statistical Association. To appear. · Zbl 1428.62515
[30] Owhadi, H. (2015). “Bayesian numerical homogenization.” Multiscale Modeling & Simulation, 13(3): 812-828. · Zbl 1322.35002 · doi:10.1137/140974596
[31] Parker, A. and Fox, C. (2012). “Sampling Gaussian distributions in Krylov spaces with conjugate gradients.” SIAM Journal on Scientific Computing, 34(3): B312-B334. · Zbl 1246.65057 · doi:10.1137/110831404
[32] Rasmussen, C. E. (2004). “Gaussian Processes in Machine Learning.” In Advances in Intelligent Data Analysis VIII, 63-71. Berlin, Heidelberg: Springer Berlin Heidelberg. · Zbl 1120.68436
[33] Reinarz, A., Dodwell, T., Fletcher, T., Seelinger, L., Butler, R., and Scheichl, R. (2018). “Dune-composites - A new framework for high-performance finite element modelling of laminates.” Composite Structures, 184: 269-278.
[34] Saad, Y. (1994). “ILUT: A dual threshold incomplete LU factorization.” Numerical Linear Algebra with Applications, 1(4): 387-402. · Zbl 0838.65026 · doi:10.1002/nla.1680010405
[35] Saad, Y. (2003). Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, second edition. · Zbl 1031.65046
[36] Schäfer, F., Sullivan, T. J., and Owhadi, H. (2017). “Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity.” arXiv:1706.02205. · Zbl 1461.65067
[37] Somersalo, E., Cheney, M., and Isaacson, D. (1992). “Existence and uniqueness for electrode models for electric current computed tomography.” SIAM Journal on Applied Mathematics, 52(4): 1023-1040. · Zbl 0759.35055 · doi:10.1137/0152060
[38] Stuart, A. M. (2010). “Inverse problems: A Bayesian perspective.” Acta Numerica, 19: 451-559. · Zbl 1242.65142 · doi:10.1017/S0962492910000061
[39] Tikhonov, A. N. (1963). “On the solution of ill-posed problems and the method of regularization.” In Doklady Akademii Nauk, volume 151, 501-504. Russian Academy of Sciences.
[40] Traub, J. F., Wasilkowski, G. W., and Woźniakowski, H. (1988). Information-Based Complexity. Computer Science and Scientific Computing. Academic Press, Inc., Boston, MA. With contributions by A. G. Werschulz and T. Boult. · Zbl 0654.94004
[41] Wikle, C. K., Milliff, R. F., Nychka, D., and Berliner, L. M. (2001). “Spatiotemporal Hierarchical Bayesian Modeling Tropical Ocean Surface Winds.” Journal of the American Statistical Association, 96(454): 382-397. · Zbl 1022.62117 · doi:10.1198/016214501753168109
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.