Efficient generalized Golub-Kahan based methods for dynamic inverse problems. (English) Zbl 1385.65034
Summary: We consider efficient methods for computing solutions to and estimating uncertainties in dynamic inverse problems, where the parameters of interest may change during the measurement procedure. Compared to static inverse problems, incorporating prior information in both space and time in a Bayesian framework can become computationally intensive, in part, due to the large number of unknown parameters. In these problems, explicit computation of the square root and/or inverse of the prior covariance matrix is not possible, so we consider efficient, iterative, matrix-free methods based on the generalized Golub-Kahan bidiagonalization that allow automatic regularization parameter and variance estimation. We demonstrate that these methods for dynamic inversion can be more flexible than standard methods and develop efficient implementations that can exploit structure in the prior, as well as possible structure in the forward model. Numerical examples from photoacoustic tomography, space-time deblurring, and passive seismic tomography demonstrate the range of applicability and effectiveness of the described approaches. Specifically, in passive seismic tomography, we demonstrate our approach on both synthetic and real data. To demonstrate the scalability of our algorithm, we solve a dynamic inverse problem with approximately \(43\, 000\) measurements and 7.8 million unknowns in under 40s on a standard desktop.
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
Keywords:
dynamic inversion; Bayesian methods; Tikhonov regularization; generalized Golub-Kahan; matern covariance kernels; tomographicReferences:
| [1] | Arioli, M., Generalized Golub-Kahan bidiagonalization and stopping criteria, SIAM J. Matrix Anal. Appl., 34, 571-592, (2013) · Zbl 1273.65041 · doi:10.1137/120866543 |
| [2] | Arioli, M.; Orban, D., Iterative methods for symmetric quasi-definite linear systems—part I: Theory, Cahier du GERAD G-2013-32 (Montréal, QC, Canada), (2013) |
| [3] | Benbow, S. J., Solving generalized least-squares problems with LSQR, SIAM J. Matrix Anal. Appl., 21, 166-177, (1999) · Zbl 0945.65041 · doi:10.1137/S0895479897321830 |
| [4] | Bui-Thanh, T.; Burstedde, C.; Ghattas, O.; Martin, J.; Stadler, G.; Wilcox, L. C., Extreme-scale UQ for Bayesian inverse problems governed by PDEs, (2012) |
| [5] | Bui-Thanh, T.; Ghattas, O.; Martin, J.; Stadler, G., 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, A2494-A2523, (2013) · Zbl 1287.35087 · doi:10.1137/12089586X |
| [6] | Calvetti, D.; Somersalo, E., Priorconditioners for linear systems, Inverse problems, 21, 1397-1418, (2005) · Zbl 1087.65044 · doi:10.1088/0266-5611/21/4/014 |
| [7] | Calvetti, D., Preconditioned iterative methods for linear discrete ill-posed problems from a Bayesian inversion perspective, J. Comput. Appl. Math, 198, 378-395, (2007) · Zbl 1101.65043 · doi:10.1016/j.cam.2005.10.038 |
| [8] | Chung, J.; Nguyen, L., Motion estimation and correction in photoacoustic tomographic reconstruction, SIAM J. Imaging Sci., 10, 216-242, (2017) · Zbl 1364.53070 · doi:10.1137/16M1082901 |
| [9] | Chung, J.; Palmer, K., A hybrid LSMR algorithm for large-scale Tikhonov regularization, SIAM J. Sci. Comput., 37, S562-S580, (2015) · Zbl 1325.65057 · doi:10.1137/140975024 |
| [10] | Chung, J.; Saibaba, A., Generalized hybrid iterative methods for large-scale Bayesian inverse problems, SIAM J. Sci. Comput., 39, S24-S46, (2017) · Zbl 1422.65065 · doi:10.1137/16M1081968 |
| [11] | Chung, J. M.; Kilmer, M. E.; O’Leary, D. P., A framework for regularization via operator approximation, SIAM J. Sci. Comput., 37, B332-B359, (2015) · Zbl 1320.65058 · doi:10.1137/130945363 |
| [12] | Chung, J.; Nagy, J. G.; O’Leary, D. P., A weighted GCV method for Lanczos hybrid regularization, Electron. Trans. Numer. Anal., 28, 149-167, (2008) · Zbl 1171.65029 |
| [13] | Donoho, D. L., De-noising by soft-thresholding, IEEE Trans. Inf. Theory, 41, 613-627, (1995) · Zbl 0820.62002 · doi:10.1109/18.382009 |
| [14] | Flath, H. P.; Wilcox, L. C.; Akçelik, V.; Hill, J.; van Bloemen Waanders, B.; Ghattas, O., Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations, SIAM J. Sci. Comput., 33, 407-432, (2011) · Zbl 1229.65174 · doi:10.1137/090780717 |
| [15] | Fuentes, M., Testing for separability of spatial—temporal covariance functions, J. Stat. Plan. Inference, 136, 447-466, (2006) · Zbl 1077.62076 · doi:10.1016/j.jspi.2004.07.004 |
| [16] | Gazzola, S.; Novati, P.; Russo, M. R., On Krylov projection methods and Tikhonov regularization, Electron. Trans. Numer. Anal, 44, 83-123, (2015) · Zbl 1312.65065 |
| [17] | Genton, M. G., Separable approximations of space-time covariance matrices, Environmetrics, 18, 681-695, (2007) · doi:10.1002/env.854 |
| [18] | Gneiting, T.; Genton, M. G.; Guttorp, P., Geostatistical space-time models, stationarity, separability, and full symmetry, Monogr. Stat. Appl. Probab., 107, 151, (2006) · Zbl 1282.86019 |
| [19] | Golub, G. H.; Kahan, W., Calculating the singular values and pseudoinverse of a matrix, SIAM J. Numer. Anal., 2, 205-224, (1965) · Zbl 0194.18201 · doi:10.1137/0702016 |
| [20] | Golub, G. H.; Heath, M.; Wahba, G., Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 215-223, (1979) · Zbl 0461.62059 · doi:10.1080/00401706.1979.10489751 |
| [21] | Hahn, B. N., Efficient algorithms for linear dynamic inverse problems with known motion, Inverse Problems, 30, (2014) · Zbl 1291.65370 · doi:10.1088/0266-5611/30/3/035008 |
| [22] | Hahn, B. N., Dynamic linear inverse problems with moderate movements of the object: Ill-posedness and regularization, Inverse Problems Imaging, 9, 395-413, (2015) · Zbl 1332.65193 · doi:10.3934/ipi.2015.9.395 |
| [23] | Hanke, M.; Hansen, P. C., Regularization methods for large-scale problems, Surv. Math. Ind., 3, 253-315, (1993) · Zbl 0805.65058 |
| [24] | Hansen, P. C., Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 6, 1-35, (1994) · Zbl 0789.65029 · doi:10.1007/BF02149761 |
| [25] | Hansen, P. C., Discrete Inverse Problems: Insight and Algorithms, (2010), Philadelphia: SIAM, Philadelphia · Zbl 1197.65054 |
| [26] | Kamm, J.; Nagy, J. G., Kronecker product and SVD approximations in image restoration, Linear Algebra Appl., 284, 177-192, (1998) · Zbl 0936.65052 · doi:10.1016/S0024-3795(98)10024-1 |
| [27] | Katsevich, A.; Silver, M.; Zamyatin, A., Local tomography and the motion estimation problem, SIAM J. Imaging Sci., 4, 200-219, (2011) · Zbl 1220.65182 · doi:10.1137/100796728 |
| [28] | Kilmer, M. E.; O’Leary, D. P., Choosing regularization parameters in iterative methods for ill-posed problems, SIAM J. Matrix Anal. Appl., 22, 1204-1221, (2001) · Zbl 0983.65056 · doi:10.1137/S0895479899345960 |
| [29] | Kim, K.; Kim, B.; Kim, M.; Lee, Y.; Vauhkonen, M., Image reconstruction in time-varying electrical impedance tomography based on the extended Kalman filter, Meas. Sci. Technol., 12, 1032, (2001) · doi:10.1088/0957-0233/12/8/307 |
| [30] | Kyriakidis, P. C.; Journel, A. G., Geostatistical space—time models: a review, Math. Geol., 31, 651-684, (1999) · Zbl 0970.86013 · doi:10.1023/A:1007528426688 |
| [31] | Laub, A. J., Matrix Analysis for Scientists & Engineers, (2005), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1077.15001 |
| [32] | Li, J. Y.; Ambikasaran, S.; Darve, E. F.; Kitanidis, P. K., A Kalman filter powered by \(\mathcal{H}^2\)-matrices for quasi-continuous data assimilation problems, Water Resour. Res., (2014) |
| [33] | Lou, Y.; Wang, K.; Oraevsky, A. A.; Anastasio, M. A., Impact of nonstationary optical illumination on image reconstruction in optoacoustic tomography, JOSA A, 33, 2333-2347, (2016) · doi:10.1364/JOSAA.33.002333 |
| [34] | Luxbacher, K.; Westman, E.; Swanson, P.; Karfakis, M., Three-dimensional time-lapse velocity tomography of an underground longwall panel, Int. J. Rock Mech. Min. Sci., 45, 478-485, (2008) · doi:10.1016/j.ijrmms.2007.07.015 |
| [35] | Ma, X.; Westman, E. C.; Fahrman, B. P.; Thibodeau, D., Imaging of temporal stress redistribution due to triggered seismicity at a deep nickel mine, Geomech. Energy Environ., 5, 55-64, (2016) · doi:10.1016/j.gete.2016.01.001 |
| [36] | Nagy, J. G.; Ng, M. K.; Perrone, L., Kronecker product approximation for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25, 829-841, (2004) · Zbl 1068.65055 · doi:10.1137/S0895479802419580 |
| [37] | Nenna, V.; Pidlisecky, A.; Knight, R., Application of an extended Kalman filter approach to inversion of time-lapse electrical resistivity imaging data for monitoring recharge, Water Resour. Res., 47, (2011) · doi:10.1029/2010WR010120 |
| [38] | Orban, D.; Arioli, M., Iterative Solution of Symmetric Quasi-Definite Linear Systems, (2017), Philadelphia: SIAM, Philadelphia · Zbl 1409.65004 |
| [39] | Paninski, L., Fast Kalman filtering on quasilinear dendritic trees, J. Comput. Neurosci., 28, 211-228, (2010) · doi:10.1007/s10827-009-0200-4 |
| [40] | Parks, M. L.; De Sturler, E.; Mackey, G.; Johnson, D. D.; Maiti, S., Recycling Krylov subspaces for sequences of linear systems, SIAM J. Sci. Comput., 28, 1651-1674, (2006) · Zbl 1123.65022 · doi:10.1137/040607277 |
| [41] | Pnevmatikakis, E. A.; Rad, K. R.; Huggins, J.; Paninski, L., Fast Kalman filtering and forward-backward smoothing via a low-rank perturbative approach, J. Comput. Graph. Stat., 23, 316-339, (2014) · doi:10.1080/10618600.2012.760461 |
| [42] | Rashid, A.; Kim, S.; Liu, D.; Kim, K., A dynamic oppositional biogeography-based optimization approach for time-varying electrical impedance tomography, Physiol. Meas., 37, 820, (2016) · doi:10.1088/0967-3334/37/6/820 |
| [43] | Rasmussen, C. E.; Williams, C. K., Gaussian Processes for Machine Learning, vol 2, (2006), Cambridge, MA: MIT Press, Cambridge, MA · Zbl 1177.68165 |
| [44] | Renaut, R. A.; Hnětynková, I.; Mead, J., Regularization parameter estimation for large-scale Tikhonov regularization using {\it a priori} information, Comput. Stat. Data Anal., 54, 3430-3445, (2010) · Zbl 1284.62156 · doi:10.1016/j.csda.2009.05.026 |
| [45] | Renaut, R. A.; Vatankhah, S.; Ardestani, V. E., Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV, SIAM J. Sci. Comput., 39, B221-B243, (2017) · Zbl 1360.65115 · doi:10.1137/15M1037925 |
| [46] | Saad, Y., Iterative Methods for Sparse Linear Systems, (2003), Philadelphia: SIAM, Philadelphia · Zbl 1002.65042 |
| [47] | Saibaba, A. K.; Ambikasaran, S.; Yue Li, J.; Kitanidis, P. K.; Darve, E. F., Application of Hierarchical matrices to linear inverse problems in geostatistics, Oil Gas Sci. Technol., 67, 857, (2012) · doi:10.2516/ogst/2012064 |
| [48] | Saibaba, A. K.; Kitanidis, P. K., Efficient methods for large-scale linear inversion using a geostatistical approach, Water Resour. Res., 48, (2012) · doi:10.1029/2011WR011778 |
| [49] | Saibaba, A. K.; Kitanidis, P. K., Fast computation of uncertainty quantification measures in the geostatistical approach to solve inverse problems, Adv. Water Resour, 82, 124-138, (2015) · doi:10.1016/j.advwatres.2015.04.012 |
| [50] | Saibaba, A. K.; Miller, E. L.; Kitanidis, P. K., Fast Kalman filter using hierarchical matrices and a low-rank perturbative approach, Inverse Problems, 31, (2015) · Zbl 1323.35214 · doi:10.1088/0266-5611/31/1/015009 |
| [51] | Sbarbaro, D.; Vauhkonen, M.; Johansen, T., State estimation and inverse problems in electrical impedance tomography: observability, convergence and regularization, Inverse Problems, 31, (2015) · Zbl 1323.35215 · doi:10.1088/0266-5611/31/4/045004 |
| [52] | Schmitt, U.; Louis, A. K., Efficient algorithms for the regularization of dynamic inverse problems: I. Theory, Inverse Problems, 18, 645, (2002) · Zbl 1003.65049 · doi:10.1088/0266-5611/18/3/308 |
| [53] | Schmitt, U.; Louis, A. K.; Wolters, C. H.; Vauhkonen, M., Efficient algorithms for the regularization of dynamic inverse problems: II. Applications, Inverse Problems, 18, 659, (2002) · Zbl 1003.65050 · doi:10.1088/0266-5611/18/3/309 |
| [54] | Sheng, Q.; Wang, K.; Matthews, T. P.; Xia, J.; Zhu, L.; Wang, L. V.; Anastasio, M. A., A constrained variable projection reconstruction method for photoacoustic computed tomography without accurate knowledge of transducer responses, IEEE Trans. Med. Imaging, 34, 2443-2458, (2015) · doi:10.1109/TMI.2015.2437356 |
| [55] | Soleimani, M.; Vauhkonen, M.; Yang, W.; Peyton, A.; Kim, B. S.; Ma, X., Dynamic imaging in electrical capacitance tomography and electromagnetic induction tomography using a Kalman filter, Meas. Sci. Technol., 18, 3287, (2007) · doi:10.1088/0957-0233/18/11/004 |
| [56] | Spantini, A.; Solonen, A.; Cui, T.; Martin, J.; Tenorio, L.; Marzouk, Y., Optimal low-rank approximations of Bayesian linear inverse problems, SIAM J. Sci. Comput., 37, A2451-A2487, (2015) · Zbl 1325.62060 · doi:10.1137/140977308 |
| [57] | Van Loan, C. F.; Pitsianis, N.; Moonen, M. S., Approximation with Kronecker products, Linear Algebra for Large Scale and Real-Time Applications, 293-314, (1993), New York: Springer, New York · Zbl 0813.65078 · doi:10.1007/978-94-015-8196-7_17 |
| [58] | Vauhkonen, M.; Karjalainen, P. A.; Kaipio, J. P., A Kalman filter approach to track fast impedance changes in electrical impedance tomography, IEEE Trans. Biomed. Eng., 45, 486-493, (1998) · doi:10.1109/10.664204 |
| [59] | Vogel, C. R., Computational Methods for Inverse Problems, (2002), Philadelphia: SIAM, Philadelphia · Zbl 1008.65103 |
| [60] | Wang, K.; Anastasio, M. A., Photoacoustic and thermoacoustic tomography: image formation principles, Handbook of Mathematical Methods in Imaging, 781-815, (2011), New York: Springer, New York · Zbl 1259.78035 · doi:10.1007/978-0-387-92920-0_18 |
| [61] | Wang, K.; Xia, J.; Li, C.; Wang, L. V.; Anastasio, M. A., Fast spatiotemporal image reconstruction based on low-rank matrix estimation for dynamic photoacoustic computed tomography, J. Biomed. Opt., 19, (2014) · doi:10.1117/1.JBO.19.5.056007 |
| [62] | Westman, E.; Luxbacher, K.; Schafrik, S., Passive seismic tomography for three-dimensional time-lapse imaging of mining-induced rock mass changes, Leading Edge, 31, 338-345, (2012) · doi:10.1190/1.3694902 |
| [63] | Zhang, H.; Sarkar, S.; Toksöz, M. N.; Kuleli, H. S.; Al-Kindy, F., Passive seismic tomography using induced seismicity at a petroleum field in oman, Geophysics, 74, WCB57-WCB69, (2009) · doi:10.1190/1.3253059 |
| [64] | Zhang, J.; Wang, K.; Yang, Y.; Anastasio, M. A., Simultaneous reconstruction of speed-of-sound and optical absorption properties in photoacoustic tomography via a time-domain iterative algorithm, Biomedical Optics, p 68561F, (2008) · doi:10.1117/12.764171 |
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.
