×

zbMATH — the first resource for mathematics

Optimal low-rank approximations of Bayesian linear inverse problems. (English) Zbl 1325.62060

MSC:
62F15 Bayesian inference
15A29 Inverse problems in linear algebra
92C55 Biomedical imaging and signal processing
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] V. Akçelik, G. Biros, O. Ghattas, J. Hill, D. Keyes, and B. van Bloemen Waanders, Parallel algorithms for PDE-constrained optimization, Parallel Process. Sci. Comput., 20 (2006), p. 291.
[2] H. Auvinen, J. M. Bardsley, H. Haario, and T. Kauranne, Large-scale Kalman filtering using the limited memory BFGS method, Electron. Trans. Numer. Anal., 35 (2009), pp. 217–233. · Zbl 1188.65084
[3] H. Auvinen, J. M. Bardsley, H. Haario, and T. Kauranne, 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
[4] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Software Environ. Tools 11, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[5] R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.
[6] T. Bui-Than, C. Burstedde, O. Ghattas, J. Martin, G. Stadler, and L. Wilcox, 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, 2012, p. 3.
[7] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems: I. Inverse shape scattering of acoustic waves, Inverse Problems, 28 (2012), 055001. · Zbl 1239.78006
[8] T. Bui-Thanh, O. Ghattas, and D. Higdon, 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
[9] T. Bui-Thanh, O. Ghattas, J. Martin, and G. Stadler, A computational framework for infinite-dimensional Bayesian inverse problems part I: The linearized case, with application to global seismic inversion, SIAM J. Sci. Comput., 35 (2013), pp. A2494–A2523. · Zbl 1287.35087
[10] D. Calvetti, Preconditioned iterative methods for linear discrete ill-posed problems from a Bayesian inversion perspective, J. Comput. Appl. Math., 198 (2007), pp. 378–395. · Zbl 1101.65043
[11] D. Calvetti, B. Lewis, and L. Reichel, On the regularizing properties of the GMRES method, Numer. Math., 91 (2002), pp. 605–625. · Zbl 1022.65044
[12] D. Calvetti, D. McGivney, and E. Somersalo, Left and right preconditioning for electrical impedance tomography with structural information, Inverse Problems, 28 (2012), 055015. · Zbl 1243.65133
[13] D. Calvetti and E. Somersalo, Priorconditioners for linear systems, Inverse Problems, 21 (2005), p. 1397. · Zbl 1087.65044
[14] B. P. Carlin and T. A. Louis, Bayesian Methods for Data Analysis, 3rd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2009. · Zbl 1165.62003
[15] R. A. Christensen, Plane Answers to Complex Questions: The Theory of Linear Models, Springer-Verlag, Berlin, 1987. · Zbl 0645.62076
[16] J. Chung and M. Chung, Computing optimal low-rank matrix approximations for image processing, in Proceedings of the Asilomar Conference on Signals, Systems and Computers, IEEE, New York, 2013, pp. 670–674.
[17] J. Chung and M. Chung, An efficient approach for computing optimal low-rank regularized inverse matrices, Inverse Problems, 30 (2014), 114009. · Zbl 1305.65130
[18] J. Chung, M. Chung, and D. P. O’Leary, Designing optimal spectral filters for inverse problems, SIAM J. Sci. Comput., 33 (2011), pp. 3132–3152. · Zbl 1269.65040
[19] J. Chung, M. Chung, and D. P. O’Leary, Optimal filters from calibration data for image deconvolution with data acquisition error, J. Math. Imaging Vis., 44 (2012), pp. 366–374. · Zbl 1255.94011
[20] J. Chung, M. Chung, and D. P. O’Leary, Optimal regularized low rank inverse approximation, Linear Algebra Appl., 468 (2015), pp. 260–269. · Zbl 1307.65048
[21] T. Cui, K. J. H. Law, and Y. Marzouk, Dimension-independent likelihood-informed MCMC, arXiv:1411.3688, 2014. · Zbl 1349.65009
[22] T. Cui, J. Martin, Y. Marzouk, A. Solonen, and A. Spantini, Likelihood-informed dimension reduction for nonlinear inverse problems, Inverse Problems, 30 (2014), 114015. · Zbl 1310.62030
[23] J. Cullum and W. Donath, A block Lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matrices, in Proceedings of the IEEE Conference on Decision and Control Including the 13th Symposium on Adaptive Processes, IEEE, New York, 1974, pp. 505–509.
[24] C. R. Dietrich and G. N. Newsam, 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
[25] L. Dykes and L. Reichel, Simplified gsvd computations for the solution of linear discrete ill-posed problems, J. Comput. Appl. Math., 255 (2014), pp. 15–27. · Zbl 1291.65117
[26] C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika, 1 (1936), pp. 211–218. · JFM 62.1075.02
[27] G. Evensen, Data Assimilation, Springer, Berlin, 2007. · Zbl 1157.86001
[28] H. P. Flath, L. 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), pp. 407–432. · Zbl 1229.65174
[29] W. Förstner and B. Moonen, A metric for covariance matrices, in Geodesy: The Challenge of the 3rd Millennium, Springer, Berlin, 2003, pp. 299–309.
[30] C. Fox and A. Parker, Convergence in variance of Chebyshev accelerated Gibbs samplers, SIAM J. Sci. Comput., 36 (2014), pp. A124–A147. · Zbl 1291.65097
[31] S. Friedland and A. Torokhti, Generalized rank-constrained matrix approximations, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 656–659. · Zbl 1144.15004
[32] G. H. Golub and C. F. Van Loan, Matrix Computations, Vol. 3, Johns Hopkins University Press, Baltimore, 2012. · Zbl 1268.65037
[33] G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, Math. Software, 3 (1977), pp. 361–377. · Zbl 0407.68040
[34] G. H. Golub and Q. Ye, An inverse free preconditioned krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 24 (2002), pp. 312–334. · Zbl 1016.65017
[35] N. Halko, P. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217–288. · Zbl 1269.65043
[36] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Res. Notes in Math. Ser. 327, Longman, Harlow, UK, 1995. · Zbl 0830.65043
[37] M. Hanke and P. C. Hansen, Regularization methods for large-scale problems, Surv. Math. Ind., 3 (1993), pp. 253–315. · Zbl 0805.65058
[38] P. C. Hansen, Regularization, GSVD and truncated GSVD, BIT, 29 (1989), pp. 491–504.
[39] P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, Monogr. Math. Model. Comput. 4, SIAM, Philadelphia, 1998.
[40] J. Heikkinen, Statistical Inversion Theory in X-Ray Tomography, Master’s thesis, Lappeenranta University of Technology, Finland, 2008.
[41] M. R. Hestenes, Pseudoinversus and conjugate gradients, Comm. ACM, 18 (1975), pp. 40–43. · Zbl 0304.65029
[42] M. R. Hestenes and E. Stiefel, Methods of Conjugate Gradients for Solving Linear Systems, Vol. 49, National Bureau of Standards Washington, DC, 1952. · Zbl 0048.09901
[43] L. Homa, D. Calvetti, A. Hoover, and E. Somersalo, Bayesian preconditioned CGLS for source separation in MEG time series, SIAM J. Sci. Comput., 35 (2013), pp. B778–B798. · Zbl 1273.35315
[44] Y. Hua and W. Liu, Generalized Karhunen-Loève transform, IEEE Signal Process. Lett., 5 (1998), pp. 141–142.
[45] W. James and C. Stein, Estimation with quadratic loss, in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, 1961, pp. 361–379. · Zbl 1281.62026
[46] W. Kahan and B. N. Parlett, How Far Should You Go with the Lanczos Process, No UCB/ERL-M78/48, Electronics Research Lab, University of California, Berkeley, 1978. · Zbl 0345.65017
[47] J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Springer, Berlin, 2005. · Zbl 1068.65022
[48] R. E. Kalman, A new approach to linear filtering and prediction problems, J. Fluids Engrg., 82 (1960), pp. 35–45.
[49] S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp., (1966), pp. 369–378. · Zbl 0156.16202
[50] C. Lanczos, An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators, U.S. Government Press Office, 1950. · Zbl 0045.39702
[51] E. L. Lehmann and G. Casella, Theory of Point Estimation, Springer-Verlag, Berlin, 1998. · Zbl 0916.62017
[52] R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, Software Environ. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[53] A. S. Lewis, Derivatives of spectral functions, Math. Oper. Res., 21 (1996), pp. 576–588. · Zbl 0860.49017
[54] W. Li and O. A. Cirpka, Efficient geostatistical inverse methods for structured and unstructured grids, Water Resources Res., 42 (2006), W06402.
[55] C. Lieberman, K. Fidkowski, K. Willcox, and B. van Bloemen Waanders, Hessian-based model reduction: Large-scale inversion and prediction, Internat. J. Numer. Methods Fluids, 71 (2013), pp. 135–150.
[56] C. Lieberman, K. Willcox, and O. Ghattas, Parameter and state model reduction for large-scale statistical inverse problems, SIAM J. Sci. Comput., 32 (2010), pp. 2523–2542. · Zbl 1217.65123
[57] F. Lindgren, H. Rue, and J. 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, 73 (2011), pp. 423–498. · Zbl 1274.62360
[58] D. V. Lindley and A. F. M. Smith, Bayes estimates for the linear model, J. R. Stat. Soc. Ser. B, 34 (1972), pp. 1–41. · Zbl 0246.62050
[59] D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Math. Program., 45 (1989), pp. 503–528. · Zbl 0696.90048
[60] J. Martin, L. Wilcox, C. Burstedde, and O. Ghattas, 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
[61] Y. Marzouk and H. N. Najm, Dimensionality reduction and polynomial chaos acceleration of Bayesian inference in inverse problems, J. Comput. Phys., 228 (2009), pp. 1862–1902. · Zbl 1161.65308
[62] X. Meng, M. A. Saunders, and M. W. Mahoney, LSRN: A parallel iterative solver for strongly over-or underdetermined systems, SIAM J. Sci. Comput., 36 (2014), pp. C95–C118. · Zbl 1298.65053
[63] E. H. Moore, On the reciprocal of the general algebraic matrix, Bull. Amer. Math. Soc., 26, pp. 394–395.
[64] J. Nocedal, Updating quasi-Newton matrices with limited storage, Math. Comput., 35 (1980), pp. 773–782. · Zbl 0464.65037
[65] C. C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph.D. thesis, University of London, 1971.
[66] C. C. Paige, Computational variants of the Lanczos method for the eigenproblem, IMA J. Appl. Math., 10 (1972), pp. 373–381. · Zbl 0253.65020
[67] C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, IMA J. Appl. Math., 18 (1976), pp. 341–349. · Zbl 0347.65018
[68] C. C. Paige and M. A. Saunders, Towards a generalized singular value decomposition, SIAM J. Numer. Anal., 18 (1981), pp. 398–405. · Zbl 0471.65018
[69] C. C. Paige and M. A. Saunders, Algorithm 583: LSQR: Sparse linear equations and least squares problems, ACM Trans. Math. Software, 8 (1982), pp. 195–209.
[70] L. Pardo, Statistical Inference Based on Divergence Measures, CRC Press, Boca Raton, FL, 2005. · Zbl 1118.62008
[71] A. Parker and C. Fox, Sampling Gaussian distributions in Krylov spaces with conjugate gradients, SIAM J. Sci. Comput., 34 (2012), pp. B312–B334. · Zbl 1246.65057
[72] R. Penrose, A generalized inverse for matrices, Math. Proc. Cambridge Philos. Soc., 51 (1955), pp. 406–413. · Zbl 0065.24603
[73] Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal., 17 (1980), pp. 687–706. · Zbl 0456.65016
[74] A. H. Sameh and J. A. Wisniewski, A trace minimization algorithm for the generalized eigenvalue problem, SIAM J. Numer. Anal., 19 (1982), pp. 1243–1259. · Zbl 0493.65017
[75] C. Schillings and C. Schwab, Scaling Limits in Computational Bayesian Inversion, Research report 2014-26, ETH-Zürich, 2014. · Zbl 1358.65013
[76] A. Solonen, H. Haario, J. Hakkarainen, H. Auvinen, I. Amour, and T. Kauranne, Variational ensemble Kalman filtering using limited memory BFGS, Electron. Trans. Numer. Anal., 39 (2012), pp. 271–285. · Zbl 1321.93060
[77] D. Sondermann, Best approximate solutions to matrix equations under rank restrictions, Statist. Papers, 27 (1986), pp. 57–66. · Zbl 0588.62103
[78] G. W. Stewart, The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal., 17 (1980), pp. 403–409. · Zbl 0443.65027
[79] A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numer., 19 (2010), pp. 451–559. · Zbl 1242.65142
[80] A. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math. Dokl., 5 (1963), pp. 1035–1038. · Zbl 0141.11001
[81] C. F. Van Loan, Generalizing the singular value decomposition, SIAM J. Numer. Anal., 13 (1976), pp. 76–83. · Zbl 0338.65022
[82] A. T. A. Wood and G. Chan, Simulation of stationary Gaussian processes in [0, 1]d, J. Comput. Graph. Statist., 3 (1994), pp. 409–432.
[83] S. J. Wright and J. Nocedal, Numerical Optimization, Vol. 2, Springer, New York, 1999. · Zbl 0930.65067
[84] Y. Yue and P. L. Speckman, Nonstationary spatial Gaussian Markov random fields, J. Comput. Graphical 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.