×

Generalized hybrid iterative methods for large-scale Bayesian inverse problems. (English) Zbl 1422.65065

Summary: We develop a generalized hybrid iterative approach for computing solutions to large-scale Bayesian inverse problems. We consider a hybrid algorithm based on the generalized Golub-Kahan bidiagonalization for computing Tikhonov regularized solutions to problems where explicit computation of the square root and inverse of the covariance kernel for the prior covariance matrix is not feasible. This is useful for large-scale problems where covariance kernels are defined on irregular grids or are available only via matrix-vector multiplication, e.g., those from the Matérn class. We show that iterates are equivalent to LSQR iterates applied to a directly regularized Tikhonov problem, after a transformation of variables, and we provide connections to a generalized singular value decomposition filtered solution. Our approach shares many benefits of standard hybrid methods such as avoiding semiconvergence and automatically estimating the regularization parameter. Numerical examples from image processing demonstrate the effectiveness of the described approaches.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F30 Other matrix algorithms (MSC2010)
15A29 Inverse problems in linear algebra
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Ambikasaran, J. Y. Li, P. K. Kitanidis, and E. Darve, {\it Large-scale stochastic linear inversion using hierarchical matrices}, Comput. Geosci., 17 (2013), pp. 913-927. · Zbl 1395.62050
[2] M. Arioli, {\it Generalized Golub-Kahan bidiagonalization and stopping criteria}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 571-592. · Zbl 1273.65041
[3] S. Arridge, M. Betcke, and L. Harhanen, {\it Iterated preconditioned LSQR method for inverse problems on unstructured grids}, Inverse Problems, 30 (2014), 075009. · Zbl 1321.65094
[4] F. Bazán and L. Borges, {\it GKB-FP: An algorithm for large-scale discrete ill-posed problems}, BIT., 50 (2010), pp. 481-507. · Zbl 1207.65039
[5] J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, {\it Rank-one modification of the symmetric eigenproblem}, Numer. Math., 31 (1978), pp. 31-48. · Zbl 0369.65007
[6] D. Calvetti, {\it 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
[7] D. Calvetti and E. Somersalo, {\it Priorconditioners for linear systems}, Inverse Problems, 21 (2005), pp. 1397-1418. · Zbl 1087.65044
[8] D. Calvetti and E. Somersalo, {\it An Introduction to Bayesian Scientific Computing: Ten Lectures on Subjective Computing}, Vol. 2, Springer, New York, 2007. · Zbl 1137.65010
[9] J. Chung, E. Haber, and J. G. Nagy, {\it Numerical methods for coupled super-resolution}, Inverse Problems, 22 (2006), pp. 1261-1272. · Zbl 1147.93302
[10] J. Chung and J. G. Nagy, {\it An efficient iterative approach for large-scale separable nonlinear inverse problems}, SIAM J. Sci. Comput., 31 (2010), pp. 4654-4674. · Zbl 1205.65160
[11] J. Chung, J. G. Nagy, and D. P. O’Leary, {\it A weighted GCV method for Lanczos hybrid regularization}, Electron. Trans. Numer. Anal., 28 (2008), pp. 149-167. · Zbl 1171.65029
[12] J. Chung and K. Palmer, {\it A hybrid LSMR algorithm for large-scale Tikhonov regularization}, SIAM J. Sci. Comput., 37 (2015), pp. S562-S580. · Zbl 1325.65057
[13] D. L. Donoho, {\it De-noising by soft-thresholding}, IEEE Trans. Inform. Theory, 41 (1995), pp. 613-627. · Zbl 0820.62002
[14] S. Farsiu, D. Robinson, M. Elad, and P. Milanfar, {\it Advances and challenges in super-resolution}, Internat. J. Imaging Systems Technology, 14 (2004), pp. 47-57.
[15] 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
[16] S. Gazzola and J. G. Nagy, {\it Generalized Arnoldi-Tikhonov method for sparse reconstruction}, SIAM J. Sci. Comput., 36 (2014), pp. B225-B247. · Zbl 1296.65061
[17] S. Gazzola, P. Novati, and M. R. Russo, {\it On Krylov projection methods and Tikhonov regularization}, Electron. Trans. Numer. Anal., 44 (2015), pp. 83-123. · Zbl 1312.65065
[18] G. H. Golub, {\it Some modified matrix eigenvalue problems}, SIAM Rev., 15 (1973), pp. 318-334. · Zbl 0254.65027
[19] G. H. Golub, M. Heath, and G. Wahba, {\it Generalized cross-validation as a method for choosing a good ridge parameter}, Technometrics, 21 (1979), pp. 215-223. · Zbl 0461.62059
[20] G. H. Golub and W. Kahan, {\it Calculating the singular values and pseudoinverse of a matrix}, SIAM J. Numer. Anal., 2 (1965), pp. 205-224. · Zbl 0194.18201
[21] G. H. Golub, F. T. Luk, and M. L. Overton, {\it A block Lanczos method for computing the singular values and corresponding singular vectors of a matrix}, ACM Trans. Math Software, 7 (1981), pp. 149-169. · Zbl 0466.65022
[22] M. Hanke and P. C. Hansen, {\it Regularization methods for large-scale problems}, Surv. Math. Industry, 3 (1993), pp. 253-315. · Zbl 0805.65058
[23] P. C. Hansen, {\it Regularization tools: A MATLAB package for analysis and solution of discrete ill-posed problems}, Numer. Algorithms, 6 (1994), pp. 1-35. · Zbl 0789.65029
[24] P. C. Hansen, {\it Discrete Inverse Problems: Insight and Algorithms}, SIAM, Philadelphia, 2010. · Zbl 1197.65054
[25] P. C. Hansen, J. G. Nagy, and D. P. O’leary, {\it Deblurring Images: Matrices, Spectra, and Filtering}, Fundam. Algorithms 3, SIAM, Philadelphia, 2006. · Zbl 1112.68127
[26] I. Hnětynková, M. Plešinger, and Z. Strakoš, {\it The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data}, BIT., 49 (2009), pp. 669-696. · Zbl 1184.65044
[27] M. E. Hochstenbach and L. Reichel, {\it An iterative method for Tikhonov regularization with a general linear regularization operator}, J. Integral Equations Appl., 22 (2010), pp. 463-480. · Zbl 1210.65092
[28] M. E. Hochstenbach, L. Reichel, and X. Yu, {\it A Golub-Kahan-type reduction method for matrix pairs}, J. Sci. Comput., 65 (2015), pp. 767-789. · Zbl 1329.65082
[29] R. A. Horn and C. R. Johnson, {\it Matrix Analysis}, Cambridge University Press, Cambridge, UK, 2012.
[30] T. K. Jensen and P. C. Hansen, {\it Iterative regularization with minimum-residual methods}, BIT, 47 (2007), pp. 103-120. · Zbl 1113.65037
[31] M. E. Kilmer, P. C. Hansen, and M. I. Espan͂ol, {\it A projection-based approach to general-form Tikhonov regularization}, SIAM J. Sci. Comput., 29 (2007), pp. 315-330. · Zbl 1140.65030
[32] M. E. Kilmer and D. P. O’Leary, {\it Choosing regularization parameters in iterative methods for ill-posed problems}, SIAM J. Matrix Anal. Appl., 22 (2001), pp. 1204-1221. · Zbl 0983.65056
[33] 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. R. Stat. Soc. Ser. B Stat. Methodol., 73 (2011), pp. 423-498. · Zbl 1274.62360
[34] C. D. Meyer, {\it Matrix Analysis and Applied Linear Algebra}, Vol. 2, SIAM, Philadelphia, 2000.
[35] J. Modersitzki, {\it Numerical Methods for Image Registration}, Oxford University Press, New York, 2003. · Zbl 1055.68140
[36] W. Nowak, S. Tenkleve, and O. Cirpka, {\it Efficient computation of linearized cross-covariance and auto-covariance matrices of interdependent quantities}, Math. Geol., 35 (2003), pp. 53-66. · Zbl 1302.86028
[37] D. P. O’Leary and J. A. Simmons, {\it A bidiagonalization-regularization procedure for large scale discretizations of ill-posed problems}, SIAM J. Sci. Statist. Comput., 2 (1981), pp. 474-489. · Zbl 0469.65089
[38] C. C. Paige and M. A. Saunders, {\it Algorithm 583, LSQR: Sparse linear equations and least-squares problems}, ACM Trans. Math. Software, 8 (1982), pp. 195-209.
[39] 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
[40] S. C. Park, M. K. Park, and M. G. Kang, {\it Super-resolution image reconstruction: A technical overview}, IEEE, Signal Process. Mag. 20 (2003), pp. 21-36.
[41] C. E. Rasmussen and C. K. Williams, {\it Gaussian Processes for Machine Learning}, MIT Press, Cambridge, MA, 2006. · Zbl 1177.68165
[42] L. Reichel, F. Sgallari, and Q. Ye, {\it Tikhonov regularization based on generalized Krylov subspace methods}, Appl. Numer. Math., 62 (2012), pp. 1215-1228. · Zbl 1246.65068
[43] R. A. Renaut, I. Hnětynková, and J. Mead, {\it Regularization parameter estimation for large-scale Tikhonov regularization using a priori information}, Comput. Statist. Data Anal., 54 (2010), pp. 3430-3445. · Zbl 1284.62156
[44] R. A. Renaut, S. Vatankhah, and V. E. Ardestani, {\it Hybrid and Iteratively Reweighted Regularization by Unbiased Predictive Risk and Weighted GCV}, preprint, , 2015. · Zbl 1360.65115
[45] Y. Saad, {\it 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
[46] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, SIAM, Philadelphia, 2003. · Zbl 1031.65046
[47] A. Saibaba and P. Kitanidis, {\it Efficient methods for large-scale linear inversion using a geostatistical approach}, Water Resources Res., 48 (2012), W05522.
[48] R. C. Thompson, {\it The behavior of eigenvalues and singular values under perturbations of restricted rank}, Linear Algebra Appl., 13 (1976), pp. 69-78. · Zbl 0343.15007
[49] C. F. Van Loan, {\it Generalizing the singular value decomposition}, SIAM J. Numer. Anal., 13 (1976), pp. 76-83. · Zbl 0338.65022
[50] C. Vogel, {\it Computational Methods for Inverse Problems}, SIAM, Philadelphia, 2002. · Zbl 1008.65103
[51] J. H. Wilkinson, {\it The Algebraic Eigenvalue Problem}, Numer. Math. Sci. Comput. 87, Oxford University Press, New York, 1965. · Zbl 0258.65037
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.