On global randomized block Kaczmarz method for image reconstruction

Ranran Li; Hao Liu; Ranran Li; Hao Liu

doi:10.3934/era.2022075

Electronic Research Archive

2022, Volume 30, Issue 4: 1442-1453. doi: 10.3934/era.2022075

Previous Article Next Article

Research article Special Issues

On global randomized block Kaczmarz method for image reconstruction

Ranran Li ¹,
Hao Liu ^{1,2
,
,}

1.
Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2.
Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles (NUAA), MIIT, Nanjing 211106, China

Received: 22 December 2021 Revised: 10 March 2022 Accepted: 10 March 2022 Published: 21 March 2022

Image reconstruction represents an important technique applied in various fields such as medicine, biology, materials science, nondestructive testing, and so forth. In this paper, we transform the problem of image reconstruction into the problem of solving linear systems with multiple right-hand sides. Based on the idea of K-means clustering, we propose the global randomized block Kaczmarz method, so as to solve the problem of the linear systems with multiple right-hand sides effectively and use this method to image reconstruction. Theoretical analysis proves the convergence of this method, and the simulation results demonstrate the performance of this method in image reconstruction.
- linear systems with multiple right-hand sides,
- randomized iteration,
- block Kaczmarz method,
- convergence property,
- image accuracy
Citation: Ranran Li, Hao Liu. On global randomized block Kaczmarz method for image reconstruction[J]. Electronic Research Archive, 2022, 30(4): 1442-1453. doi: 10.3934/era.2022075

Related Papers:

Abstract

Image reconstruction represents an important technique applied in various fields such as medicine, biology, materials science, nondestructive testing, and so forth. In this paper, we transform the problem of image reconstruction into the problem of solving linear systems with multiple right-hand sides. Based on the idea of K-means clustering, we propose the global randomized block Kaczmarz method, so as to solve the problem of the linear systems with multiple right-hand sides effectively and use this method to image reconstruction. Theoretical analysis proves the convergence of this method, and the simulation results demonstrate the performance of this method in image reconstruction.

References

[1]	J. A. Fessler, B. P. Sutton, Nonuniform fast fourier transforms using min-max interpolation, IEEE Trans. Signal Process., 51 (2003), 560–574. https://doi.org/10.1109/TSP.2002.807005 doi: 10.1109/TSP.2002.807005
[2]	A. C. Kak, M. Slaney, G. Wang, Principles of computerized tomographic imaging, Med. Phys., 29 (2002), 107–107. https://doi.org/10.1118/1.1455742 doi: 10.1118/1.1455742
[3]	S. F. Gull, G. J. Daniell, Image reconstruction from incomplete and noisy data, Med. Phys., 272 (1978), 686–690. https://doi.org/10.1038/272686a0 doi: 10.1038/272686a0
[4]	G. L. Zeng, Image reconstruction a tutorial, Comput. Med. Imaging Graphics, 25 (2001), 97–103. https://doi.org/10.1016/S0895-6111(00)00059-8 doi: 10.1016/S0895-6111(00)00059-8
[5]	F. Natterer, F. Wubbeling, G. Wang, Mathematical methods in image reconstruction, Med. Phys., 29 (2002), 107–108. https://doi.org/10.1118/1.1455744 doi: 10.1118/1.1455744
[6]	S. C. Park, M. K. Park, M. G. Kang, Super-resolution image reconstruction: a technical overview, IEEE Signal Processing Mag., 20 (2003), 21–36. https://doi.org/10.1109/MSP.2003.1203207 doi: 10.1109/MSP.2003.1203207
[7]	X. L. Zhao, T. Z. Huang, X. M. Gu, L. J. Deng, Vector extrapolation based Landweber method for discrete ill-posed problems, Math. Probl. Eng., 2017 (2017), 1375716. https://doi.org/10.1155/2017/1375716 doi: 10.1155/2017/1375716
[8]	S. Helgason, The Radon Transform (2nd ed.), Progress in Mathematics, Springer, Boston, MA, 2007. https://doi.org/10.1007/978-1-4757-1463-0
[9]	G. T. Herman, Fundamentals of Computerized Tomography: Image Reconstruction from Projections, Springer, Dordrecht, 2009.
[10]	A. Rahman, System of Linear Equations in Computed Tomography (CT), MSc Thesis, BRAC University, Dhaka, Bangladesh, 2018.
[11]	T. G. Feeman, X-rays, Springer New York, 2010. https://doi.org/10.1007/978-0-387-92712-1_1
[12]	O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1994.
[13]	Z. Z. Bai, C. H. Jin, Column-decomposed relaxation methods for the overdetermined systems of linear equations, Int. J. Appl. Math. Comput. Sci., 13 (2003), 71–82.
[14]	C. Brezinski, Projection Methods for Systems of Equations, Elsevier Science B.V., Amsterdam, 1997.
[15]	Y. Censor, G. T. Herman, J. Ming, A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin, J.Fourier Anal. Appl., 15 (2009), 431–436. https://doi.org/10.1007/s00041-009-9077-x doi: 10.1007/s00041-009-9077-x
[16]	S. Kaczmarz, Angen$\ddot{a}$herte aufl$\ddot{o}$sung von systemen linearer gleichungen, Bull. Int. Acad. Pol. Sci. Lett. Ser. A, 35 (1937), 355–357.
[17]	M. A. Brooks, A Survey of Algebraic Algorithms in Computerize Tomography, MSc Thesis, University of Ontario Institute of Technology, Oshawa, Ontario, 2010.
[18]	Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Program., 42 (1988), 307–325. https://doi.org/10.1007/BF01589408 doi: 10.1007/BF01589408
[19]	D. A. Lorenz, S. Wenger, F. Sch$\ddot{o}$pfer, A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing, in 2014 IEEE international conference on image processing (ICIP), (2014), 1347–1351. https://doi.org/10.1109/ICIP.2014.7025269
[20]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103–120. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
[21]	T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J.Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[22]	Z. Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[23]	Z. Z. Bai, W. T. Wu, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), 21–26. https://doi.org/10.1016/j.aml.2018.03.008 doi: 10.1016/j.aml.2018.03.008
[24]	Y. Q. Niu, B. Zheng, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Appl. Math. Lett., 104 (2020), 106294–106294. https://doi.org/10.1016/j.aml.2020.106294 doi: 10.1016/j.aml.2020.106294
[25]	J. Q. Chen, Z. D. Huang, On the error estimate of the randomized double block Kaczmarz method, Appl. Math. Comput., 370 (2020), 124907–124907. https://doi.org/10.1016/j.amc.2019.124907 doi: 10.1016/j.amc.2019.124907
[26]	D. P. O'Leary, The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29 (1980), 293–322. https://doi.org/10.1016/0024-3795(80)90247-5 doi: 10.1016/0024-3795(80)90247-5
[27]	V. Simoncini, E. Gallopoulos, Convergence properties of block GMRES and matrix polynomials, Linear Algebra Appl., 247 (1996), 97–119. https://doi.org/10.1016/0024-3795(95)00093-3 doi: 10.1016/0024-3795(95)00093-3
[28]	V. Simoncini, E. Gallopolous, An iterative method for nonsymmetric systems with multiple right-hand sides, SIAM J. Sci. Computi., 16 (2006), 917–933. https://doi.org/10.1137/0916053 doi: 10.1137/0916053
[29]	V. Simoncini, A stabilized QMR version of block BiCG, SIAM J. Matrix Anal. Appl., 18 (2006), 419–434. https://doi.org/10.1137/S0895479894264673 doi: 10.1137/S0895479894264673
[30]	Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, 2003.
[31]	R. W. Freund, M. Malhotra, A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides, Linear Algebra Appl., 254 (1997), 119–157. https://doi.org/10.1016/S0024-3795(96)00529-0 doi: 10.1016/S0024-3795(96)00529-0
[32]	R. Sides R, A. E. Guennouni, K. Jbilou, H. Sadok, A block version of BiCGSTAB for linear systems with multiple right-hand sides, Electron. Trans. Numer. Anal., 16 (2003), 129–142. https://doi.org/10.1038/021396a0 doi: 10.1038/021396a0
[33]	H. Dai, Block bidiagonalization methods for multiple nonsymmetric linear systems, Numer. Math. J. Chin. Univ., 02 (2001), 209–225.
[34]	G. D. Gu, A seed method for solving nonsymmetric linear systems with multiple right-hand sides, Int. J. Comput. Math., 79 (2002), 307–326. https://doi.org/10.1080/00207160211931 doi: 10.1080/00207160211931
[35]	A. K. Jain, Data clustering: 50 years beyond K-means, Pattern Recognit. Lett., 31 (2009), 651–666. https://doi.org/10.1016/j.patrec.2009.09.011 doi: 10.1016/j.patrec.2009.09.011
[36]	Y. J. Li, K. C. Mo, H. S. Ye, Accelerating random Kaczmarz algorithm based on clustering information, in Proceedings of the AAAI Conference on Artificial Intelligence, 30 (2016), 1823–1829.
[37]	X. L. Jiang, K. Zhang, J. F. Yin, Randomized block Kaczmarz methods with k-means clustering for solving large linear systems, J. Comput. Appl. Math., 403 (2022), 113828. https://doi.org/10.1016/j.cam.2021.113828 doi: 10.1016/j.cam.2021.113828
[38]	J. R. Sendra, J. Sendra, Computation of Moore-Penrose generalized inverses of matrices with meromorphic function entries, Appl. Math. Comput., 313 (2017), 355–366. https://doi.org/10.1016/j.amc.2017.06.007 doi: 10.1016/j.amc.2017.06.007
[39]	G. Vijayalakshmi, P. Vindhya, Comparison of algebraic reconstruction methods in computed tomography, Int. J. Comput. Sci. Inf. Technol., 5 (2014), 6007–6009. https://doi.org/10.3934/dcdsb.2004.4.1065 doi: 10.3934/dcdsb.2004.4.1065

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)