For solving large-scale consistent linear system, a greedy randomized Kaczmarz method with oblique projection and a maximal weighted residual Kaczmarz method with oblique projection are proposed. By using oblique projection, these two methods greatly reduce the number of iteration steps and running time to find the minimum norm solution, especially when the rows of matrix are highly linearly correlated. Theoretical proof and numerical results show that the greedy randomized Kaczmarz method with oblique projection and the maximal weighted residual Kaczmarz method with oblique projection are more effective than the greedy randomized Kaczmarz method and the maximal weighted residual Kaczmarz method respectively.
Citation: Fang Wang, Weiguo Li, Wendi Bao, Li Liu. Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection[J]. Electronic Research Archive, 2022, 30(4): 1158-1186. doi: 10.3934/era.2022062
For solving large-scale consistent linear system, a greedy randomized Kaczmarz method with oblique projection and a maximal weighted residual Kaczmarz method with oblique projection are proposed. By using oblique projection, these two methods greatly reduce the number of iteration steps and running time to find the minimum norm solution, especially when the rows of matrix are highly linearly correlated. Theoretical proof and numerical results show that the greedy randomized Kaczmarz method with oblique projection and the maximal weighted residual Kaczmarz method with oblique projection are more effective than the greedy randomized Kaczmarz method and the maximal weighted residual Kaczmarz method respectively.
| [1] |
S. Kaczmarz, Approximate solution of systems of linear equations, Int. J. Control, 57 (1993), 1269–1271. https://doi.org/10.1080/00207179308934446 doi: 10.1080/00207179308934446
|
| [2] |
R. Gordon, R. Bender, G. Herman, Algebraic reconstruction techniques (ART) for three dimensional electron microscopy and X-ray photography, J. Theor. Biol., 29 (1970), 471–481. https://doi.org/10.1016/0022-5193(70)90109-8 doi: 10.1016/0022-5193(70)90109-8
|
| [3] |
A. J. Devaney, A filtered backpropagation algorithm for diffraction tomography, Ultrason. Imaging, 4 (1982), 336–350. https://doi.org/10.1016/0161-7346(82)90017-7 doi: 10.1016/0161-7346(82)90017-7
|
| [4] |
S. J. Wernecke, L. R. D'Addario, Maximum entropy image reconstruction, IEEE Trans. Comput., 26 (1997), 351–364. https://doi.org/10.1109/TC.1977.1674845 doi: 10.1109/TC.1977.1674845
|
| [5] |
J. Skilling, R. K. Bryan, Maximum entropy image reconstruction-general algorithm, Mon. Not. R. Astron. Soc., 211 (1984), 111–124. https://doi.org/10.1109/TC.1977.1674845 doi: 10.1109/TC.1977.1674845
|
| [6] | W. Guo, H. Chen, W. Geng, L. Li, A modified Kaczmarz algorithm for computerized tomographic image reconstruction, in International Conference on Biomedical Engineering and Informatics IEEE, (2019), 1–4. https://doi.org/10.1109/BMEI.2009.5305654 |
| [7] |
S. Lee, H. J. Kim, Noise properties of reconstructed images in a kilo-voltage on-board imaging system with iterative reconstruction techniques: A phantom study, Phys. Med., 30 (2014), 365–373. https://doi.org/10.1016/j.ejmp.2013.11.003 doi: 10.1016/j.ejmp.2013.11.003
|
| [8] |
D. Carmona-Ballester, J. M. Trujillo-Sevilla, Bonaque-Gonz$\acute{a}$les, $\acute{O}$. G$\acute{o}$mez-C$\acute{a}$rdenes, J. M. Rodr$\acute{i}$guez-Ramos, Weighted nonnegative tensor factorization for atmospheric tomography reconstruction, Astron. Astrophys., 614 (2018), A41. https://doi.org/10.1051/0004-6361/201832597 doi: 10.1051/0004-6361/201832597
|
| [9] |
T. Li, D. Isaacson, J. C. Newell, G. J. Saulnier, Adaptive techniques in electrical impedance tomography reconstruction, Physiol. Meas., 35 (2014), 1111–1124. https://doi.org/10.1088/0967-3334/35/6/1111 doi: 10.1088/0967-3334/35/6/1111
|
| [10] |
R. Ramlau, M. Rosensteiner, An efficient solution to the atmospheric turbulence tomography problem using Kaczmarz iteration, Inverse Probl., 28 (2012), 095004. https://doi.org/10.1088/0266-5611/28/9/095004 doi: 10.1088/0266-5611/28/9/095004
|
| [11] |
G. Thoppe, V. S. Borkar, D. Manjunath, A stochastic Kaczmarz algorithm for network tomography, Automatica, 50 (2014), 910–914. https://doi.org/10.1016/j.automatica.2013.12.016 doi: 10.1016/j.automatica.2013.12.016
|
| [12] |
A. Hefny, D. Needell, A. Ramdas, Rows versus columns: randomized Kaczmarz or Gauss-Seidel for ridge regression, SIAM J. Sci. Comput., 39 (2017), S528–S542. https://doi.org/10.1137/16M1077891 doi: 10.1137/16M1077891
|
| [13] | V. Borkar, N. Karamchandani, S. Mirani, Randomized Kaczmarz for rank aggregation from pairwise comparisons, in 2016 IEEE Information Theory Workshop (ITW), (2016), 389–393. https://doi.org/10.1109/ITW.2016.7606862 |
| [14] |
J. Loera, J. Haddock, D. Needell, A sampling Kaczmarz-Motzkin algorithm for linear feasibility, SIAM J. Sci. Comput., 39 (2017), S66–S87. https://doi.org/10.1137/16m1073807 doi: 10.1137/16m1073807
|
| [15] |
H. Q. Guan, R. Gordon, A projection access order for speedy convergence of ART (algebraic reconstruction technique): a multilevel scheme for computed tomography, Phys. Med. Biol., 39 (1994), 2005–2022. https://doi.org/10.1088/0031-9155/39/11/013 doi: 10.1088/0031-9155/39/11/013
|
| [16] |
X. Intes, V. Ntziachristos, J. P. Culver, A. Yodh, B. Chance, Projection access order in algebraic reconstruction technique for diffuse optical tomography, Phys. Med. Biol., 47 (2002), N1–N10. https://doi.org/10.1088/0031-9155/47/1/401 doi: 10.1088/0031-9155/47/1/401
|
| [17] |
X. L. Xu, J. S. Liow, S. C. Strother, Iterative algebraic reconstruction algorithms for emission computed tomography: A unified framework and its application to positron emission tomography, Med. Phys., 20 (1993), 1675–1684. https://doi.org/10.1118/1.596954 doi: 10.1118/1.596954
|
| [18] |
K. Tanabe, Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17 (1971), 203–214. https://doi.org/10.1007/BF01436376 doi: 10.1007/BF01436376
|
| [19] |
C. G. Kang, H. Zhou, The extension of convergence rates of kaczmarz type methods, J. Comput. Appl. Math., 382 (2021), 113099. http://doi.org/10.1016/j.cam.2020.113099 doi: 10.1016/j.cam.2020.113099
|
| [20] |
C. G. Kang, Convergence rates of the Kaczmarz-Tanabe method for linear systems, J. Comput. Appl. Math., 394 (2021), 113577. https://doi.org/10.1016/j.cam.2021.113577 doi: 10.1016/j.cam.2021.113577
|
| [21] | S. F. Mccormick, The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space, Indiana Univ. Math. J., 26 (1977), 1137–1150. http://www.jstor.org/stable/24891603 |
| [22] |
K. Du, H. Gao, A new theoretical estimate for the convergence rate of the maximal residual Kaczmarz algorithm, Numer. Math. Theor. Meth. Appl., 12 (2019), 627–639. https://doi.org/10.4208/nmtma.OA-2018-0039 doi: 10.4208/nmtma.OA-2018-0039
|
| [23] |
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
|
| [24] |
D. Needell, J. A. Tropp, Paved with good intentions: analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
|
| [25] |
D. Needell, R. Zhao, A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484 (2015), 322–343. https://doi.org/10.1016/j.laa.2015.06.027 doi: 10.1016/j.laa.2015.06.027
|
| [26] |
I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. Appl., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
|
| [27] |
K. Du, W. T. Si, X. H. Sun, Randomized extended average block Kaczmarz for solving least squares, SIAM J. Sci. Comput., 42 (2020), A3541–A3559. https://doi.org/10.1137/20M1312629 doi: 10.1137/20M1312629
|
| [28] |
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
|
| [29] |
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
|
| [30] |
X. Yang, A geometric probability randomized Kaczmarz method for large scale linear systems, Appl. Numer. Math., 164 (2021), 139–160. https://doi.org/10.1016/j.apnum.2020.10.016 doi: 10.1016/j.apnum.2020.10.016
|
| [31] |
J. J. Zhang, A new greedy Kaczmarz algorithm for the solution of very large linear systems, Appl. Math. Lett., 91 (2019), 207–212. https://doi.org/10.1016/j.aml.2018.12.022 doi: 10.1016/j.aml.2018.12.022
|
| [32] |
Y. Liu, C. Q. Gu, Variant of greedy randomized Kaczmarz for ridge regression, Appl. Numer. Math., 143 (2019), 223–246. https://doi.org/10.1016/j.apnum.2019.04.008 doi: 10.1016/j.apnum.2019.04.008
|
| [33] |
Z. Z. Bai, W. T. Wu, On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Linear Algebra Appl., 578 (2019), 225–250. https://doi.org/10.1016/j.laa.2019.05.005 doi: 10.1016/j.laa.2019.05.005
|
| [34] |
A. Ma, D. Needell, A. Ramdas, Convergence properties of the randomized extended gauss-seidel and kaczmarz methods, SIAM J. Matrix Anal. Appl., 36 (2015), 1590–1604. https://doi.org/10.1137/15M1014425 doi: 10.1137/15M1014425
|
| [35] |
K. Du, Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms, Numer. Linear Algebra Appl., 26 (2019), e2233. https://doi.org/10.1002/nla.2233 doi: 10.1002/nla.2233
|
| [36] |
D. Needell, R. Ward, Two-subspace projection method for coherent overdetermined systems, J. Fourier Anal. Appl., 19 (2013), 256–269. https://doi.org/10.1007/s00041-012-9248-z doi: 10.1007/s00041-012-9248-z
|
| [37] |
J. Liu, S. J. Wright, An accelerated randomized Kaczmarz algorithm, Math. Comput., 85 (2016), 153–178. https://doi.org/10.1090/mcom/2971 doi: 10.1090/mcom/2971
|
| [38] |
C. PoPa, T. Preclik, H. K$\ddot{o}$stler, U. R$\ddot{u}$de, On Kaczmarz's projection iteration as a direct solver for linear least squares problems, Linear Algebra Appl., 436 (2012), 389–404. https://doi.org/10.1016/j.laa.2011.02.017 doi: 10.1016/j.laa.2011.02.017
|
| [39] | Y. J. Guan, W. G. Li, L. L. Xing, T. T. Qiao, A note on convergence rate of randomized Kaczmarz method, Calcolo, 57 (2020), 1–11. https://doi.org/10.1007@s10092-020-00376-4 |
| [40] |
Q. F. Wang, W. G. Li, W. D. Bao, X. Q. Gao, Nonlinear Kaczmarz algorithms and their convergence, J. Comput. Appl. Math., 399 (2022), 113720. https://doi.org/10.1016/j.cam.2021.113720 doi: 10.1016/j.cam.2021.113720
|
| [41] |
F. Sch$\ddot{o}$pfer, D. A. Lorenz, Linear convergence of the randomized sparse Kaczmarz method, Math. Program., 1 (2016), 1–28. https://doi.org/10.1007/s10107-017-1229-1 doi: 10.1007/s10107-017-1229-1
|
| [42] |
D. Leventhal, A. Lewis, Randomized methods for linear constraints: convergence rates and conditioning, Math. Oper. Res., 35 (2010), 641–654. https://doi.org/10.1287/moor.1100.0456 doi: 10.1287/moor.1100.0456
|
| [43] |
Z. Z. Bai, W. T. Wu, On greedy randomized coordinate descent methods for solving large linear least-squares problems, Numer. Linear Algebra Appl., 26 (2019), 1–15. https://doi.org/10.1002/nla.2237 doi: 10.1002/nla.2237
|
| [44] |
K. W. Chang, C. J. Hsieh, C. J. Lin, Coordinate descent method for large-scale l2-loss linear support vector machines, J. Mach. Learn. Res, 9 (2008), 1369–1398. https://doi.org/10.5555/1390681.1442778 doi: 10.5555/1390681.1442778
|
| [45] |
Z. Lu, L. Xiao, On the complexity analysis of randomized block-coordinate descent methods, Math. Program., 152 (2015), 615–642. https://doi.org/10.1007/s10107-014-0800-2 doi: 10.1007/s10107-014-0800-2
|
| [46] |
I. Necoara, Y. Nesterov, F. Glineur, Random block coordinate descent methods for linearly constrained optimization over networks, J. Optim. Theory Appl., 173 (2017), 227–254. https://doi.org/10.1007/s10957-016-1058-z doi: 10.1007/s10957-016-1058-z
|
| [47] |
Y. Nesterov, S. Stich, Efficiency of the accelerated coordinate descent method on structured optimization problems, SIAM J. Optim., 27 (2017), 110–123. https://doi.org/10.1137/16M1060182 doi: 10.1137/16M1060182
|
| [48] |
P. Richt$\acute{a}$rik, M. Tak$\acute{a}\check{c}$, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144 (2014), 1–38. https://doi.org/10.1007/s10107-012-0614-z doi: 10.1007/s10107-012-0614-z
|
| [49] |
S. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), 3–34. https://doi.org/10.1007/s10107-015-0892-3 doi: 10.1007/s10107-015-0892-3
|
| [50] |
J. H. Zhang, J. H. Guo, On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems, Appl. Numer. Math., 157 (2020), 372–384. https://doi.org/10.1016/j.apnum.2020.06.014 doi: 10.1016/j.apnum.2020.06.014
|
| [51] | C. Popa, Projection algorithms–-classical results and developments, Applications to image reconstruction, LAP Lambert Academic Publishing, Saarbrucken, 2012 |
| [52] |
D. A. Lorenz, S. Rose, Frank Sch$\ddot{o}$pfer, The randomized Kaczmarz method with mismatched adjoint, BIT, 58 (2018), 1–20. https://doi.org/10.1007/s10543-018-0717-x doi: 10.1007/s10543-018-0717-x
|
| [53] | W. G. Li, Q. F. Wang, W. D. Bao, L. Liu, On Kaczmarz method with oblique projection for solving large overdetermined linear systems, preprint, arXiv: math/2106.13368 |
| [54] |
W. T. Wu, On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems, Numer. Algor., 89 (2022), 1–31. https://doi.org/10.1007/s11075-021-01104-x doi: 10.1007/s11075-021-01104-x
|
| [55] | A. Ben-Israel, T. N. E. Thomas, Generalized inverses: Theory and applications, Springer Science & Business Media, 2003. |
| [56] |
F. Wang, W. G. Li, W. D. Bao, Z. L. Lv, Gauss-Seidel method with oblique direction, Results Appl. Math., 12 (2021), 100180. https://doi.org/10.1016/j.rinam.2021.100180 doi: 10.1016/j.rinam.2021.100180
|
| [57] |
T. A. Davis, Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1–25. https://doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663
|
| [58] |
P. C. Hansen, J. S. Jorgensen, AIR tools II: algebraic iterative reconstruction methods, improved implementation, Numer. Algorithms, 79 (2018), 107–137. https://doi.org/10.1007/s11075-017-0430-x doi: 10.1007/s11075-017-0430-x
|
| [59] |
L. H. Landweber, An iteration formula for Fredholm integral equations of the first kind, Am. J. Math., 73 (1951), 615–624. https://doi.org/10.2307/2372313 doi: 10.2307/2372313
|
| [60] |
Y. Saad, M. H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), 856–869. https://doi.org/10.1137/0907058 doi: 10.1137/0907058
|
| [61] |
L. Liang, Y. Xu, Adaptive landweber method to deblur images, IEEE Signal Process. Lett., 10 (2003), 129–132. https://doi.org/10.1109/LSP.2003.810012 doi: 10.1109/LSP.2003.810012
|
| [62] |
X. L. Zhao, T. Z. Huang, X. M. Gu, L. J. Deng, Vector extrapolation based Landweber method for discrete ill-posed problems, Math. Prob. Eng., 2017 (2017), 1375716. https://doi.org/10.1155/2017/1375716 doi: 10.1155/2017/1375716
|
Figures(8) / Tables(9)
Fang Wang, Weiguo Li, Wendi Bao, Li Liu. Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection[J]. Electronic Research Archive, 2022, 30(4): 1158-1186. doi: 10.3934/era.2022062
DownLoad: