An overview of iterative methods based on orthogonal projections

Document Type : Original Article

Authors

Applied Mathematics Department, School of Mathematics and computer Sciences, Iran University of Science and Technology, Tehran, Iran.

Abstract
This paper investigates the linear feasibility problem (LFP), which plays a fundamental role in image reconstruction, especially in applications such as computed tomography and signal processing. The goal is to find a point in the intersection of a finite collection of convex sets defined by linear constraints. We provide a structured overview and comparison of existing orthogonal projection-based iterative methods for solving LFPs, including sequential, simultaneous, and block-iterative algorithms. While these methods have been studied individually in the literature, our work highlights their theoretical underpinnings, practical performance, and convergence properties in a unified framework. We also revisit and refine known convergence theorems, discussing their assumptions and implications in the context of real-world reconstruction problems. The novelty of this study lies in its comprehensive synthesis of algorithmic strategies along with a critical analysis of their relative strengths, limitations, and applicability. This work aims to clarify the landscape of projection methods for LFPs and to guide the selection or development of more effective reconstruction techniques in practice.

Keywords

Subjects


[1] Aharoni, R., and Censor, Y. 1989. Block-iterative projection methods for parallel computation of solutions to convex feasibility problems. Linear Algebra and Its Applications, 165175. 1
[2] Bauschke, H. H., and Borwein, J. M. 1996. On projection algorithms for solving convex feasibility problems. SIAM review 38, 367426. doi: 10.1137/S0036144593251710 1, 2
[3] Byrne, C. 2000. Block-iterative interior point optimization methods for image reconstruction from limited data. Inverse Problems 16, 1405. doi: 10.1088/0266-5611/16/5/316 1
[4] Cegielski, A. 2012. Iterative methods for fixed point problems in Hilbert spaces, volume 2057. Springer. doi: 10.1007/978-3-642-30901-4 3.2
[5] Censor, Y. 1981. Row-action methods for huge and sparse systems and their applications. SIAM review, 23(4):444– 466. doi: 10.1137/1023097
[6] Censor, Y. 1984. Iterative methods for the convex feasibility problem. North-Holland Mathematics Studies, 8391.1
[7] Censor, Y., and Elfving, T. 2002. Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem. SIAM Journal on Matrix Analysis and Applications 24, 4058. doi: 10.1137/S089547980138705X2
[8] Censor, Y., Gordon, D., and Gordon, R. 2001. BICAV: A block-iterative parallel algorithm for sparse systems with pixel-related weighting. Medical Imaging, IEEE Transactions on 20, 10501060. doi: 10.1109/42.959302 1, 3.2, 3.11
[9] Censor, Y., Gordon, D., and Gordon, R. 2001. Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems. Parallel computing 27, 777 808. doi: 10.1016/S0167-8191(00)00100-9 1, 3.4
[10] Censor, Y., and Herman, G. T. 1987. On some optimization techniques in image reconstruction from projections. Applied Numerical Mathematics, 3(5):365391. doi: 10.1016/0168-9274(87)90028-6 1, 3.2
[11] Censor, Y., and Zenios, S. A. 1997. Parallel optimization: Theory, algorithms, and applications. Oxford University Press on Demand. 1
[12] Cimmino, G., and delle Ricerche, C. N. 1938. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Istituto per le applicazioni del calcolo. 1, 3
[13] Elfving, T. 1980. Block-iterative methods for consistent and inconsistent linear equations. Numerische Mathematik 35, 112. 1, 3.2
[14] Elfving, T., and Nikazad, T., 2009. Properties of a class of block-iterative methods. Inverse problems 25, 115011. 1
[15] Gordon, R. Bender, R. and Herman. G. T., 1970. Algebraic reconstruction techniques (art) for three-dimensional electron microscopy and x-ray photography. Journal of theoretical Biology, 29(3):471481. doi: 10.1016/0022- 5193(70)90109-8 3.3.2
[16] Gubin, L., Polyak, B., and Raik, E. 1967. The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics 7, 124. doi: 10.1016/0041-5553(67)90113-9 1
[17] Gustafsson, B. 1996. Mathematics for computer tomography. Physica Scripta, 38. doi: 10.1088/0031 8949/1996/T61/006 3.1
[18] Harshbarger, T. B., and Twieg, D. B. 1999. Iterative reconstruction of single-shot spiral mri with off resonance. IEEE transactions on medical imaging 18, 196–205. 2
[19] Herman, G. T., 1980. Image reconstruction from projections. The fundamentals of computerized tomography, 316.1
[20] Herman, G. T., 2009. Fundamentals of computerized tomography: image reconstruction from projections. Springer Science & Business Media. 1
[21] Jiang, M., and Wang, G., 2003. Convergence studies on iterative algorithms for image reconstruction. Medical Imaging, IEEE Transactions on 22, 569579. 3.12
[22] Kaczmarz, S. 1937. Angenäherte auflösung von systemen linearer gleichungen. Bulletin International de lA- cademie Polonaise des Sciences et des Lettres, 355357. 3.2
[23] Kak, A. C., and Slaney, M. 1988. Principles of computerized tomographic imaging. IEEE press. 1, 3.1
[24] Kang, C.-g., Zhou, H., 2021. The extensions of convergence rates of Kaczmarz-type methods, Journal of Computational and Applied Mathematics 113099. 1, 2
[25] Natterer, F. 1986. The mathematics of computerized tomography. John Wiley, New York. 3.1.1, 3.5, 3.6, 3.1.2
[26] Nikazad, T., and Abbasi, M., 2013. An acceleration scheme for cyclic subgradient projections method. Computational Optimization and Applications 54, 7791. 1, 3.12
[27] Nikazad, T., Abbasi, M., and Elfving, T. Error minimizing relaxation strategies in landweber and kaczmarz type iterations. 3.1
[28] Nikazad, T., Davidi, R., and Herman, G. 2012 Accelerated perturbation-resilient block-iterative projection methods with application to image reconstruction. Inverse problems 28, 035005. doi: 10.1088/0266-5611/28/3/035005 3.2,
3.3.2, 3.3.2
[29] Penfold, S., Schulte, R. W., Censor, Y., Bashkirov, V., McAllister, S., Schubert, K., and Rosenfeld, A. B. 2010. Block- iterative and string-averaging projection algorithms in proton computed tomography image reconstruction. 1
[30] Popa, C., 1995. Least-squares solution of overdetermined inconsistent linear systems using Kaczmarzs relaxation, Int. J. Comput. Math. 7989. 1
[31] Rodriguez, A., 2004. Principles of magnetic resonance imaging. Revista mexicana de física 50, 272286. 3.1.2
[32] Sørensen, H. H. B., and Hansen, P. C., 2014. Multicore performance of block algebraic iterative reconstruction methods. SIAM Journal on Scientific Computing 36, C524C546. doi: 10.1137/130920642 1
[33] Tanabe, K., 1971. Projection method for solving a singular system of linear equations and its applications, Numer. Math. 203214. 3.4
[34] Wang, G., Vannier, M. W. and Cheng. P. C., 1999. Iterative x-ray cone-beam tomography for metal artifact reduction and local region reconstruction. Microscopy and microanalysis, 5(1):58-65. doi: 10.1017/S1431927699000057 3.4, 3.1.1
[35] Steffen, R., Hill, D. R., and DuPont, H. L. (2015). Travelers diarrhea: a clinical review. Jama, 313(1), 71–80. 1
Volume 6, Issue 2
Spring 2025
Pages 112-124

  • Receive Date 10 January 2025
  • Revise Date 05 May 2025
  • Accept Date 21 June 2025