GMRES methods for tomographic reconstruction with an unmatched back projector. (English) Zbl 1489.65060
Summary: Unmatched pairs of forward and back projectors are common in X-ray CT computations for large-scale problems; they are caused by the need for fast algorithms that best utilize the computer hardware, and it is an interesting and challenging task to develop fast and easy-to-use algorithms for these cases. Our approach is to use preconditioned GMRES, in the form of the AB- and BA-GMRES algorithms, to handle the unmatched normal equations associated with an unmatched pair. These algorithms are simple to implement, they rely only on computations with the available forward and back projectors, and they do not require the tuning of any algorithm parameters. We show that these algorithms are equivalent to well-known LSQR and LSMR algorithms in the case of a matched projector. Our numerical experiments demonstrate that AB- and BA-GMRES exhibit a desired semi-convergence behavior that is comparable with LSQR/LSMR and that standard stopping rules work well. Hence, AB- and BA-GMRES are suited for large-scale CT reconstruction problems with noisy data and unmatched projector pairs.
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F10 | Iterative numerical methods for linear systems |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
CT-reconstruction; regularizing iterations; GMRES; semi-convergence; unmatched backprojector; stopping rulesReferences:
| [1] | Computed Tomography: Algorithms, Insight and Just Enough Theory, (Hansen, P. C.; Jørgensen, J. S.; Lionheart, W. R.B. (2021), SIAM: SIAM Philadelphia) · Zbl 1482.94006 |
| [2] | Hahn, K.; Schöndube, H.; Stierstorfer, K.; Hornegger, J.; Noo, F., A comparison of linear interpolation models for iterative CT reconstruction, Med. Phys., 43, 6455-6473 (2016) |
| [3] | Lalush, D. S.; Wernick, M. N., Iterative image reconstruction, (Wernick, M. N.; Aarsvold, J. N., Emission Tomography – the Fundamentals of PET and SPECT (2004), Elsevier) |
| [4] | Natterer, F., The Mathematics of Computerized Tomography (2001), SIAM: SIAM Philadelphia · Zbl 0973.92020 |
| [5] | Palenstijn, W. J.; Batenburg, K. J.; Sijbers, J., Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs), J. Struct. Biol., 176, 250-253 (2011) |
| [6] | Elfving, T.; Hansen, P. C., Unmatched projector/backprojector pairs: perturbation and convergence analysis, SIAM J. Sci. Comput., 40, A573-A591 (2018) · Zbl 1383.65035 |
| [7] | Dong, Y.; Hansen, P. C.; Hochstenbach, M. E.; Riis, N. A.B., Fixing nonconvergence of algebraic iterative reconstruction with an unmatched backprojector, SIAM J. Sci. Comput., 41, A1822-A1839 (2019) · Zbl 1420.65031 |
| [8] | Hansen, P. C.; Jørgensen, J. S., AIR Tools II: algebraic iterative reconstruction methods, improved implementation, Numer. Algorithms, 79, 107-137 (2018) · Zbl 1397.65007 |
| [9] | Couzenoux, E.; Pesquet, J.-C.; Riddell, C.; Savanier, M.; Trousset, Y., Convergence of proximal gradient algorithm in the presence of adjoint mismatch, Inverse Problems, 37, Article 065009 pp. (2021) · Zbl 1466.94004 |
| [10] | Sørensen, H. H.B.; Hansen, P. C., Multicore performance of block algebraic iterative methods, SIAM J. Sci. Comput., 36, C524-C546 (2014) · Zbl 1307.65037 |
| [11] | Hayami, K.; Yin, J.-F.; Ito, T., GMRES methods for least squares problems, SIAM J. Matrix Anal. Appl., 31, 2400-2430 (2010) · Zbl 1215.65071 |
| [12] | Donatelli, M.; Estatico, C.; Martinelli, A.; Serra-Capizzano, S., Improved image deblurring with anti-reflective boundary conditions and re-blurring, Inverse Problems, 22, 2035-2053 (2006) · Zbl 1167.65474 |
| [13] | Donatelli, M.; Martin, D.; Reichel, L., Arnoldi methods for image deblurring with anti-reflective boundary conditions, Appl. Math. Comput., 253, 135-150 (2015) · Zbl 1338.94006 |
| [14] | Sidky, E. Y.; Hansen, P. C.; Jørgensen, J. S.; Pan, X., Iterative image reconstruction for CT with unmatched projection matrices using the generalized minimal residual algorithm, (7th International Conference on Image Formation in X-Ray Computed Tomography. 7th International Conference on Image Formation in X-Ray Computed Tomography, June 12-16, 2022, Baltimore, USA (2022)), arXiv:2201.07408 |
| [15] | Morikuni, K.; Hayami, K., Convergence of inner-iteration GMRES methods for rank-deficient least squares problems, SIAM J. Matrix Anal. Appl., 36, 1, 225-250 (2015) · Zbl 1315.65041 |
| [16] | Du, Y.-S.; Hayami, K.; Zheng, N.; Morikuni, K.; Yin, J.-F., Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems, SIAM J. Sci. Comput., 43, 5, S345-S366 (2021) · Zbl 1490.65049 |
| [17] | Wedin, P.-Å., Perturbation bounds in connection with singular value decomposition, BIT, 12, 1, 99-111 (1972) · Zbl 0239.15015 |
| [18] | Stewart, G. W.; Sun, J.-G., Matrix Perturbation Theory (1990), Academic Press: Academic Press Boston · Zbl 0706.65013 |
| [19] | Hansen, P., Discrete Inverse Problems: Insight and Algorithms (2010), SIAM: SIAM Philadelphia · Zbl 1197.65054 |
| [20] | Reichel, L.; Rodriguez, G., Old and new parameter choice rules for discrete ill-posed problems, Numer. Algorithms, 63, 65-87 (2013) · Zbl 1267.65045 |
| [21] | Hansen, P. C.; Jørgensen, J. S.; Rasmussen, P. W., Stopping rules for algebraic iterative reconstruction methods in computed tomography, (21st International Conference on Computational Science and Its Applications. 21st International Conference on Computational Science and Its Applications, ICCSA (2021), IEEE), 60-70 |
| [22] | Hansen, P., Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion (1998), SIAM: SIAM Philadelphia |
| [23] | Elfving, T.; Hansen, P. C.; Nikazad, T., Semi-convergence properties of Kaczmarz’s method, Inverse Problems, 30, Article 055007 pp. (2014) · Zbl 1296.65054 |
| [24] | van Lith, B. S.; Hansen, P. C.; Hochstenbach, M. E., A twin error gauge for Kaczmarz’s iterations, SIAM J. Sci. Comput. (2021), special section Coppen Mountain 2020 · Zbl 1490.65072 |
| [25] | Calvetti, D.; Lewis, B.; Reichel, L., On the regularizing properties of the GMRES method, Numer. Math., 91, 605-625 (2002) · Zbl 1022.65044 |
| [26] | Gazzola, S.; Novati, P., Inheritance of the discrete Picard condition in Krylov subspace methods, BIT, 56, 893-918 (2016) · Zbl 1353.65023 |
| [27] | Hanke, M., Conjugate Gradient Type Methods for Ill-Posed Problems (1995), Longman Scientific & Technical: Longman Scientific & Technical Essex · Zbl 0830.65043 |
| [28] | Hanke, M., On Lanczos based methods for the regularization of discrete ill-posed problems, BIT, 41, 1008-1018 (2001) |
| [29] | Jensen, T.; Hansen, P., Iterative regularization with minimum residual methods, BIT, 47, 103-120 (2007) · Zbl 1113.65037 |
| [30] | Fong, D. C.-L.; Saunders, M., LSMR: an iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33, 2950-2991 (2011) · Zbl 1232.65052 |
| [31] | Jia, Z., Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs, Numer. Algorithms, 85, 1281-1310 (2020) · Zbl 1455.65062 |
| [32] | Hansen, P., Regularization Tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029 |
| [33] | Fong, D. C.-L., LSMR: an iterative algorithm for least-squares problems (2021), available from mathworks.com/matlabcentral/fileexchange/ 27183-lsmr-an-iterative-algorithm-for-least-squares-problems |
| [34] | van Aarle, W.; Palenstijn, W. J.; Cant, J.; Janssens, E.; Bleichrodt, R.; Dabravolski, A.; Beenhouwer, J. D.; Batenburg, K. J.; Sijbers, J., Fast and flexible X-ray tomography using the ASTRA toolbox, Opt. Express, 24, 25129-25147 (2016), available from astra-toolbox.com |
| [35] | Morozov, V., Methods for Solving Incorrectly Posed Problems (1984), Springer: Springer NY · Zbl 0549.65031 |
| [36] | Hung, C.-H.; Markham, T. L., The Moore-Penrose inverse of a partitioned matrix \(M = \left( \begin{matrix} A \& D \\ B \& C \end{matrix}\right)\), Linear Algebra Appl., 11, 1, 73-86 (1975) · Zbl 0326.15005 |
| [37] | Hung, C.-H.; Markham, T. L., The Moore-Penrose inverse of a sum of matrices, J. Aust. Math. Soc., 24, 4, 385-392 (1977) · Zbl 0376.15005 |
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.
