Dong, Yiqiu; Hansen, Per Christian; Hochstenbach, Michiel E.; Brogaard Riis, Nicolai André Fixing nonconvergence of algebraic iterative reconstruction with an unmatched backprojector. (English) Zbl 1420.65031 SIAM J. Sci. Comput. 41, No. 3, A1822-A1839 (2019). Summary: We consider algebraic iterative reconstruction methods with applications in image reconstruction. In particular, we are concerned with methods based on an unmatched projector/backprojector pair, i.e., the backprojector is not the exact adjoint or transpose of the forward projector. Such situations are common in large-scale computed tomography, and we consider the common situation where the method does not converge due to the nonsymmetry of the iteration matrix. We propose a modified algorithm that incorporates a small shift parameter, and we give the conditions that guarantee convergence of this method to a fixed point of a slightly perturbed problem. We also give perturbation bounds for this fixed point. Moreover, we discuss how to use Krylov subspace methods to efficiently estimate the leftmost eigenvalue of a certain matrix to select a proper shift parameter. The modified algorithm is illustrated with test problems from computed tomography. Cited in 8 Documents MSC: 65F10 Iterative numerical methods for linear systems 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F22 Ill-posedness and regularization problems in numerical linear algebra 15A18 Eigenvalues, singular values, and eigenvectors 15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory Keywords:unmatched transpose; algebraic iterative reconstruction; perturbation theory; leftmost eigenvalue estimation; computed tomography Software:Regularization tools; IRAM; Spot; GitHub; AIR tools; eigs; TIGRE; ASTRA PDFBibTeX XMLCite \textit{Y. Dong} et al., SIAM J. Sci. Comput. 41, No. 3, A1822--A1839 (2019; Zbl 1420.65031) Full Text: DOI arXiv References: [1] A. Biguri, M. Dosanjh, S. Hancock, and M. Soleimani, TIGRE: A MATLAB-GPU toolbox for CBCT image reconstruction, Biomed. Phys. Eng. Express, 2 (2016), 055010; the software available from https://github.com/CERN/TIGRE. [2] T. Elfving and P. C. Hansen, Unmatched projector/backprojector pairs: Perturbation and convergence analysis, SIAM J. Sci. Comput., 40 (2018), pp. A573-A591. · Zbl 1383.65035 [3] T. Elfving, P. C. Hansen, and T. Nikazad, Semiconvergence and relaxation parameters for projected SIRT algorithms, SIAM J. Sci. Comput., 34 (2012), pp. A2000-A2017. · Zbl 1254.65044 [4] W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Springer, New York, 2016. · Zbl 1347.65063 [5] P. C. Hansen, The discrete Picard condition for discrete ill-posed problems, BIT, 5 (1990), pp. 658-672. · Zbl 0723.65147 [6] P. C. Hansen, Test matrices for regularization methods, SIAM J. Sci. Comput., 16 (1995), pp. 506-512. · Zbl 0820.65020 [7] P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems, SIAM, Philadelphia, 1998. [8] P. C. Hansen, Regularization Tools Version 4.0 for MATLAB 7.3, Numer. Algorithms, 46 (2007), pp. 189-194. · Zbl 1128.65029 [9] P. C. Hansen, Oblique projections and standard-form transformations for discrete inverse problems, Numer. Linear Algebra Appl., 20 (2013), pp. 250-258. · Zbl 1289.65097 [10] P. C. Hansen and J. S. Jørgensen, AIR Tools II: Algebraic iterative reconstruction methods, improved implementation, Numer. Algorithms, 79 (2018), pp. 107-137. · Zbl 1397.65007 [11] R. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, UK, 2013. [12] P. M. Joseph, An improved algorithm for reprojecting rays through pixel images, IEEE Trans. Medical Imag., 3 (1982), pp. 192-196. [13] D. A. Lorenz, S. Rose, and F. Schöpfer, The randomized Kaczmarz method with mismatched adjoint, BIT, 58 (2018), pp. 1079-1098. · Zbl 1404.65017 [14] K. Meerbergen and D. Roose, Matrix transformations for computing rightmost eigenvalues of large sparse non-symmetric eigenvalue problems, IMA J. Numer. Anal., 16 (1996), pp. 297-346. · Zbl 0856.65033 [15] K. Meerbergen and M. Sadkane, Using Krylov approximations to the matrix exponential operator in Davidson’s method, Appl. Numer. Math., 31 (1999), pp. 331-351. · Zbl 0942.65036 [16] F. Natterer, The Mathematics of Computerized Tomography, Classics in Appl. Math. 32, SIAM, Philadelphia, 2001. · Zbl 0973.92020 [17] R. C. Nelson, S. Feuerlein, and D. T. Boll, New iterative reconstruction techniques for cardiovascular computed tomography: How do they work, and what are the advantages and disadvantages?, J. Cardiovascuar Computed Tomography, 5 (2011), pp. 286-292. [18] G. L. G. Sleijpen and H. A. Van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 401-425. · Zbl 0860.65023 [19] D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357-385. · Zbl 0763.65025 [20] G. W. Stewart, A Krylov-Schur algorithm for large eigenproblems, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 601-614. · Zbl 1003.65045 [21] G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Academic Press, Boston, 1990. [22] W. van Aarle, W. J. Palenstijn, J. Cant, E. Janssens, R. Bleichrodt, A. Dabravolski, J. De Beenhouwer, K. J. Batenburg, and J. Sijbers, Fast and flexible X-ray tomography using the ASTRA toolbox, Opt. Express, 24 (2016), pp. 25129-25147; the software available from http://www.astra-toolbox.com. [23] E. van den Berg and M. P. Friedlander, Spot–A Linear-Operator Toolbox, http://www.cs.ubc.ca/labs/scl/spot/. [24] S. van der Maar, K. J. Batenburg, and J. Sijbers, Experiences with Cell-BE and GPU for tomography; in Embedded Compter Systems: Architectures, Modeling, and Simulation, Proceedings 9th International Workshop SAMOS, K. Bertels, N. Dimopoulos, C. Silvano, and S. Wong, eds., Springer, Berlin, 2009, pp. 298-307. [25] G. L. Zeng and G. T. Gullberg, Unmatched projection/backprojection pairs in iterative reconstruction algorithms, IEEE Trans. Med. Imaging, 19 (2000), pp. 548-555. 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.