Volume 12, Issue 2
A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm

Kui Du & Han Gao

Numer. Math. Theor. Meth. Appl., 12 (2019), pp. 627-639.

Published online: 2018-12

Preview Purchase PDF 144 8455
Export citation
  • Abstract

In this note we prove a new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm for solving  a consistent linear system. The estimate depends only on quantities that are easy to compute and not on the number of equations in the system. We compare the maximal weighted residual Kaczmarz algorithm and the greedy randomized Kaczmarz algorithm by two sets of examples. Numerical results show that the maximal weighted residual Kaczmarz algorithm requires almost the same number of iterations as that of the greedy randomized Kaczmarz algorithm for underdetermined linear systems and less iterations for overdetermined linear systems. Due to less computational cost in the row index selection strategy, the maximal weighted residual Kaczmarz algorithm is more efficient than the greedy randomized Kaczmarz algorithm.

  • Keywords

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-12-627, author = {}, title = {A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2018}, volume = {12}, number = {2}, pages = {627--639}, abstract = {

In this note we prove a new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm for solving  a consistent linear system. The estimate depends only on quantities that are easy to compute and not on the number of equations in the system. We compare the maximal weighted residual Kaczmarz algorithm and the greedy randomized Kaczmarz algorithm by two sets of examples. Numerical results show that the maximal weighted residual Kaczmarz algorithm requires almost the same number of iterations as that of the greedy randomized Kaczmarz algorithm for underdetermined linear systems and less iterations for overdetermined linear systems. Due to less computational cost in the row index selection strategy, the maximal weighted residual Kaczmarz algorithm is more efficient than the greedy randomized Kaczmarz algorithm.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.OA-2018-0039}, url = {http://global-sci.org/intro/article_detail/nmtma/12912.html} }
TY - JOUR T1 - A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm JO - Numerical Mathematics: Theory, Methods and Applications VL - 2 SP - 627 EP - 639 PY - 2018 DA - 2018/12 SN - 12 DO - http://doi.org/10.4208/nmtma.OA-2018-0039 UR - https://global-sci.org/intro/article_detail/nmtma/12912.html KW - AB -

In this note we prove a new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm for solving  a consistent linear system. The estimate depends only on quantities that are easy to compute and not on the number of equations in the system. We compare the maximal weighted residual Kaczmarz algorithm and the greedy randomized Kaczmarz algorithm by two sets of examples. Numerical results show that the maximal weighted residual Kaczmarz algorithm requires almost the same number of iterations as that of the greedy randomized Kaczmarz algorithm for underdetermined linear systems and less iterations for overdetermined linear systems. Due to less computational cost in the row index selection strategy, the maximal weighted residual Kaczmarz algorithm is more efficient than the greedy randomized Kaczmarz algorithm.

Kui Du & Han Gao. (2020). A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm. Numerical Mathematics: Theory, Methods and Applications. 12 (2). 627-639. doi:10.4208/nmtma.OA-2018-0039
Copy to clipboard
The citation has been copied to your clipboard