Skip to main content
Log in

AIR Tools II: algebraic iterative reconstruction methods, improved implementation

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

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 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andersen, A. H., Kak, A. C.: Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm. Ultrason. Imaging 6, 81–94 (1984)

    Article  Google Scholar 

  2. Andersen, M. S., Hansen, P. C.: Generalized row-action methods for tomographic imaging. Numer. Algorithms 67, 121–144 (2014). https://doi.org/10.1007/s11075-013-9778-8

    Article  MathSciNet  MATH  Google Scholar 

  3. Bertsekas, D. P.: Incremental proximal methods for large scale convex optimization. Math. Prog. 129, 163–195 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  4. Björck, Å., Elfving, T.: Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations. BIT 19, 145–163 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  5. Buzug, T. M.: Computed Tomography. Springer, Berlin (2008)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  7. Censor, Y., Elfving, T., Herman, G. T., Nikazad, T.: On diagonally relaxed orthogonal projection methods. SIAM J. Sci. Comp. 30, 473–504 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  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, I. T.: A parallel subgradient projections method for the convex feasibility problem. J. Comput. Appl. Math. 18, 307–320 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  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

  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

  15. Elfving, T., Hansen, P. C., Nikazad, T.: Semi-convergence and relaxation parameters for projected SIRT algorithms. SIAM J. Sci. Comput. 34, A2000–A2017 (2012). https://doi.org/10.1137/110834640

    Article  MATH  Google Scholar 

  16. Elfving, T., Nikazad, T.: Properties of a class of block-iterative methods. Inverse Prob. 25, 115011 (2009). https://doi.org/10.1088/0266-5611/25/11/115011

    Article  MathSciNet  MATH  Google Scholar 

  17. Elfving, T., Nikazad, T.: Stopping rules for Landweber-type iteration. Inverse Prob. 23, 1417–1432 (2007). https://doi.org/10.1088/0266-5611/23/4/004

    Article  MATH  Google Scholar 

  18. Elfving, T., Nikazad, T., Hansen, P. C.: Semi-convergence and relaxation parameters for a class of SIRT algorithms. Electron. Trans. Numer. Anal. 37, 321–336 (2010)

    MathSciNet  MATH  Google Scholar 

  19. Gilbert, P.: Iterative methods for the three-dimensional reconstruction of an object from projections. J. Theor. Biol. 36, 105–117 (1972)

    Article  Google Scholar 

  20. Gordon, R, Bender, R, Herman, G. T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471–481 (1970). https://doi.org/10.1016/0022-5193(70)90109-8

    Article  Google Scholar 

  21. Hansen, P. C.: Discrete Inverse Problems: Insight and Algorithms. SIAM, Philadelphia (2010)

    Book  MATH  Google Scholar 

  22. Hansen, P. C., Kilmer, M. E., Kjeldsen, R. H.: Exploiting residual information in the parameter choice for discrete ill-posed problems. BIT Numer. Math. 46, 41–59 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  23. Hansen, P. C., Nagy, J. G., Tigkos, K.: Rotational image deblurring with sparse matrices. BIT Numer. Math. 54, 649–671 (2014). https://doi.org/10.1007/s10543-013-0464-y

    Article  MathSciNet  MATH  Google Scholar 

  24. Hansen, P. C., Saxild-Hansen, M.: AIR Tools—a MATLAB package of algebraic iterative reconstruction methods. J. Comp. Appl. Math. 236, 2167–2178 (2012). https://doi.org/10.1016/j.cam.2011.09.039

    Article  MathSciNet  MATH  Google Scholar 

  25. Herman, G. T., Lent, A.: Iterative reconstruction algorithms. Comput. Biol. Med. 6, 273–294 (1976)

    Article  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  27. Jensen, J. M., Jacobsen, B. H., Christensen-Dalsgaard, J.: Sensitivity kernels for time-distance inversion. Sol. Phys. 192, 231–239 (2000)

    Article  Google Scholar 

  28. Jørgensen, J. S., Sidky, E. Y., Hansen, P. C., Pan, X.: Empirical average-case relation between undersampling and sparsity in X-ray CT. Inverse Problems and Imaging 9, 431–446 (2015). https://doi.org/10.3934/ipi.2015.9.431

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  30. Klukowska, J., Davidi, R., Herman, G. T.: SNARK09—a software package for reconstruction of 2D images from 1D projections. Comput. Methods Programs Biomed. 110, 424–440 (2013). https://doi.org/10.1016/j.cmpb.2013.01.003. The software is available from https://www.dig.cs.gc.cuny.edu/software/snark09/index.php

    Article  Google Scholar 

  31. Kuchment, P., Kunyansky, L.: Mathematics of thermoacoustic tomography. Euro. J. Applied Math. 19, 191–224 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  32. Landweber, L.: An iteration formula for Fredholm integral of the first kind. Am. J. Math. 73, 615–624 (1951)

    Article  MathSciNet  MATH  Google Scholar 

  33. Natterer, F.: The Mathematics of Computerized Tomography. Reprinted by SIAM, Philadelphia (2001)

  34. Palenstijn, W. J., Batenburg, K. J., Sijbers, J.: Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs). J. Structural Biology 176, 250–253 (2011)

    Article  Google Scholar 

  35. Perry, K., Reeves, S.: A practical stopping rule for iterative signal restoration. IEEE Trans. Signal Proces. 42, 1829–1833 (1994)

    Article  Google Scholar 

  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

  37. Siddon, R. L.: Fast calculation of the exact radiological path for a three-dimensional CT array. Med. Phys. 12, 252–255 (1985)

    Article  Google Scholar 

  38. Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm for linear systems with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  39. Sørensen, H. H. B., Hansen, P. C.: Multicore performance of block algebraic iterative reconstruction methods. SIAM J. Sci. Comp. 36, C524–C546 (2014)

    Article  MATH  Google Scholar 

  40. TIGRE: Tomographic iterative GPU-based reconstruction toolbox, available from https://github.com/CERN/TIGRE

  41. van Aarle, W., Palenstijn, W. J., Cant, J., Janssens, E., Bleichrodt, F., Dabravolski, A., De Beenhouwer, J., Batenburg, K. J., Sijbers, J.: Fast and flexible X-ray tomography using the ASTRA toolbox. Opt. Express 24, 25129–25147 (2016). https://doi.org/10.1364/OE.24.025129. The software is available from https://www.astra-toolbox.com

    Article  Google Scholar 

  42. van der Sluis, A., van der Vorst, H. A.: SIRT- And CG-type methods for the iterative solution of sparse linear least-squares problems. Linear Algebra Appl. 130, 257–303 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  43. Vogel, C. R.: Computational Methods for Inverse Problems. SIAM, Philadelphia (2002)

    Book  MATH  Google Scholar 

  44. Watt, D. W.: Column-relaxed algebraic reconstruction algorithm for tomography with noisy data. Appl. Opt. 33, 4420–4427 (1994)

    Article  Google Scholar 

  45. Wright, S. J.: Coordinate descent algorithms. Math. Program., Ser. B 151, 3–34 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We thank Tommy Elfving for his continued help and support during this project.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Per Christian Hansen.

Additional information

This work is a part of the project HD-Tomo funded by Advanced Grant No. 291405 from the European Research Council. Networking support was provided by the EXTREMA COST Action MP1207.

The work was carried out while the author Jakob Sauer Jørgensen was with the Department of Applied Mathematics and Computer Science, Technical University of Denmark.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hansen, P.C., Jørgensen, J.S. AIR Tools II: algebraic iterative reconstruction methods, improved implementation. Numer Algor 79, 107–137 (2018). https://doi.org/10.1007/s11075-017-0430-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-017-0430-x

Keywords

Mathematics Subject Classification (2010)

Navigation