×

zbMATH — the first resource for mathematics

AIR tools II: algebraic iterative reconstruction methods, improved implementation. (English) Zbl 1397.65007
Summary: We present a MATLAB software package with efficient, robust, and flexible implementations of algebraic iterative reconstruction (AIR) methods for computing regularized solutions to discretizations of inverse problems. These methods are of particular interest in computed tomography and similar problems where they easily adapt to the particular geometry of the problem. All our methods are equipped with stopping rules as well as heuristics for computing a good relaxation parameter, and we also provide several test problems from tomography. The package is intended for users who want to experiment with algebraic iterative methods and their convergence properties. The present software is a much expanded and an improved version of the package AIR Tools from 2012, based on a new modular design. In addition to improved performance and memory use, we provide more flexible iterative methods, a column-action method, new test problems, new demo functions, and – perhaps most important – the ability to use function handles instead of (sparse) matrices, allowing larger problems to be handled.

MSC:
65-04 Software, source code, etc. for problems pertaining to numerical analysis
65F10 Iterative numerical methods for linear systems
65F22 Ill-posedness and regularization problems in numerical linear algebra
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, AH; Kak, AC, Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm, Ultrason. Imaging, 6, 81-94, (1984)
[2] Andersen, MS; Hansen, PC, Generalized row-action methods for tomographic imaging, Numer. Algorithms, 67, 121-144, (2014) · Zbl 1302.65285
[3] Bertsekas, DP, Incremental proximal methods for large scale convex optimization, Math. Prog., 129, 163-195, (2011) · Zbl 1229.90121
[4] Björck, Å; Elfving, T, Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT, 19, 145-163, (1979) · Zbl 0409.65022
[5] Buzug, T. M.: Computed Tomography. Springer, Berlin (2008)
[6] Censor, Y; Elfving, T, Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem, SIAM J. Matrix Anal. Appl., 24, 40-58, (2002) · Zbl 1028.90034
[7] Censor, Y; Elfving, T; Herman, GT; Nikazad, T, On diagonally relaxed orthogonal projection methods, SIAM J. Sci. Comp., 30, 473-504, (2007) · Zbl 1159.65317
[8] Censor, Y; Gordon, D; Gordon, R, Component averaging: an efficient iterative parallel algorithm for large sparse unstructured problems, Parallel Comput., 27, 777-808, (2001) · Zbl 0972.68189
[9] Cimmino, G, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica, XVI, Series II, Anno IX, 1, 326-333, (1938) · JFM 64.1244.02
[10] Coban, S. B.: Sophiabeads datasets project codes, May 2017. Available online from: https://sophilyplum.github.io/sophiabeads-datasets
[11] Coban, S. B., McDonald, S. A.: Sophiabeads dataset project, March 2015. Available online from: https://doi.org/10.5281/zenodo.16474
[12] Dos Santos, IT, A parallel subgradient projections method for the convex feasibility problem, J. Comput. Appl. Math., 18, 307-320, (1987) · Zbl 0623.90076
[13] Elfving, T., Hansen, P. C., Nikazad, T.: Convergence analysis for column-action methods in image reconstruction. Numerical Algorithms (2016). https://doi.org/10.1007/s11075-016-0176-x. Erratum (Fig. 3 was incorrect), https://doi.org/10.1007/s11075-016-0232-6 · Zbl 1366.65116
[14] Elfving, T., Hansen, P. C., Nikazad, T.: Semi-convergence properties of Kaczmarz’s method. Inverse Prob. 30 (2014). https://doi.org/10.1088/0266-5611/30/5/055007 · Zbl 1296.65054
[15] Elfving, T; Hansen, PC; Nikazad, T, Semi-convergence and relaxation parameters for projected SIRT algorithms, SIAM J. Sci. Comput., 34, a2000-a2017, (2012) · Zbl 1254.65044
[16] Elfving, T; Nikazad, T, Properties of a class of block-iterative methods, Inverse Prob., 25, 115011, (2009) · Zbl 1184.65036
[17] Elfving, T; Nikazad, T, Stopping rules for Landweber-type iteration, Inverse Prob., 23, 1417-1432, (2007) · Zbl 1124.65034
[18] Elfving, T; Nikazad, T; Hansen, PC, Semi-convergence and relaxation parameters for a class of SIRT algorithms, Electron. Trans. Numer. Anal., 37, 321-336, (2010) · Zbl 1205.65148
[19] Gilbert, P, Iterative methods for the three-dimensional reconstruction of an object from projections, J. Theor. Biol., 36, 105-117, (1972)
[20] Gordon, R; Bender, R; Herman, GT, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theor. Biol., 29, 471-481, (1970)
[21] Hansen, P. C.: Discrete Inverse Problems: Insight and Algorithms. SIAM, Philadelphia (2010) · Zbl 1197.65054
[22] Hansen, PC; Kilmer, ME; Kjeldsen, RH, Exploiting residual information in the parameter choice for discrete ill-posed problems, BIT Numer. Math., 46, 41-59, (2006) · Zbl 1091.65038
[23] Hansen, PC; Nagy, JG; Tigkos, K, Rotational image deblurring with sparse matrices, BIT Numer. Math., 54, 649-671, (2014) · Zbl 1302.65055
[24] Hansen, PC; Saxild-Hansen, M, AIR tools—a MATLAB package of algebraic iterative reconstruction methods, J. Comp. Appl. Math., 236, 2167-2178, (2012) · Zbl 1241.65042
[25] Herman, GT; Lent, A, Iterative reconstruction algorithms, Comput. Biol. Med., 6, 273-294, (1976)
[26] Hämarik, U; Tautenhahn, U, On the monotone error rule for parameter choice in iterative and continuous regularization methods, BIT, 41, 1029-1038, (2001)
[27] Jensen, JM; Jacobsen, BH; Christensen-Dalsgaard, J, Sensitivity kernels for time-distance inversion, Sol. Phys., 192, 231-239, (2000)
[28] Jørgensen, JS; Sidky, EY; Hansen, PC; Pan, X, Empirical average-case relation between undersampling and sparsity in X-ray CT, Inverse Problems and Imaging, 9, 431-446, (2015) · Zbl 1332.90393
[29] Kaczmarz, S, Angenäherte auflösung von systemen linearer gleichungen, Bulletin de l’Académie Polonaise des Sciences et Lettres, A35, 355-357, (1937) · Zbl 0017.31703
[30] Klukowska, J; Davidi, R; Herman, GT, SNARK09—a software package for reconstruction of 2D images from 1D projections, Comput. Methods Programs Biomed., 110, 424-440, (2013)
[31] Kuchment, P; Kunyansky, L, Mathematics of thermoacoustic tomography, Euro. J. Applied Math., 19, 191-224, (2008) · Zbl 1185.35327
[32] Landweber, L, An iteration formula for Fredholm integral of the first kind, Am. J. Math., 73, 615-624, (1951) · Zbl 0043.10602
[33] Natterer, F.: The Mathematics of Computerized Tomography. Reprinted by SIAM, Philadelphia (2001) · Zbl 0973.92020
[34] Palenstijn, WJ; Batenburg, KJ; Sijbers, J, Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs), J. Structural Biology, 176, 250-253, (2011)
[35] Perry, K; Reeves, S, A practical stopping rule for iterative signal restoration, IEEE Trans. Signal Proces., 42, 1829-1833, (1994)
[36] Rust, B. W., O’Leary, D. P.: Residual periodograms for choosing regularization parameters for ill-posed problems. Inverse Prob. 24 (2008). https://doi.org/10.1088/0266-5611/24/3/034005 · Zbl 1137.62036
[37] Siddon, RL, Fast calculation of the exact radiological path for a three-dimensional CT array, Med. Phys., 12, 252-255, (1985)
[38] Strohmer, T; Vershynin, R, A randomized Kaczmarz algorithm for linear systems with exponential convergence, J. Fourier Anal. Appl., 15, 262-278, (2009) · Zbl 1169.68052
[39] Sørensen, HHB; Hansen, PC, Multicore performance of block algebraic iterative reconstruction methods, SIAM J. Sci. Comp., 36, c524-c546, (2014) · Zbl 1307.65037
[40] TIGRE: Tomographic iterative GPU-based reconstruction toolbox, available from https://github.com/CERN/TIGRE · Zbl 1028.90034
[41] Aarle, W; Palenstijn, WJ; Cant, J; Janssens, E; Bleichrodt, F; Dabravolski, A; De Beenhouwer, J; Batenburg, KJ; Sijbers, J, Fast and flexible X-ray tomography using the ASTRA toolbox, Opt. Express, 24, 25129-25147, (2016)
[42] Sluis, A; Vorst, HA, SIRT- and CG-type methods for the iterative solution of sparse linear least-squares problems, Linear Algebra Appl., 130, 257-303, (1990) · Zbl 0702.65042
[43] Vogel, C. R.: Computational Methods for Inverse Problems. SIAM, Philadelphia (2002) · Zbl 1008.65103
[44] Watt, DW, Column-relaxed algebraic reconstruction algorithm for tomography with noisy data, Appl. Opt., 33, 4420-4427, (1994)
[45] Wright, SJ, Coordinate descent algorithms, Math. Program., Ser. B, 151, 3-34, (2015) · Zbl 1317.49038
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.