A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems

In this paper, we propose four extended Kaczmarz methods: two partially randomized methods like probability proportional to residual or residual homogenizing, and two deterministic strategies with the maximal-residual control and the maximum-distance control. Without the full column rank and overdetermined assumptions on linear systems, we provide a thorough convergence analysis in terms of expectation, and derive upper bounds for the expected convergence rates of the new extended Kaczmarz methods. Numerical experiments on Gaussian models as well as 2D image reconstruction problems demonstrate that the new extended Kaczmarz methods can be much more effective than the existing ones. Especially, the improvements of two deterministic strategies are very prominent. • Four extended Kaczmarz methods based on residuals are proposed. There are two partially randomized methods and two deterministic strategies. • Without the full column rank and overdetermined assumptions on linear systems, we provide a thorough convergence analysis in terms of expectation, and derive upper bounds for the expected convergence rates of the new extended Kaczmarz methods. • Numerical experiments on three types of matrices: (i) Random matrix; (ii) Random orthogonal matrix; (iii) Real-world matrix, and 2D image reconstruction problems are given. For the first and third types of matrices, we consider the following three cases: (1) linear systems are overdetermined and rank(A)=n; (2) linear systems are overdetermined and rank(A)< n. (3) linear systems are underdetermined. All experiments demonstrate that the new extended Kaczmarz methods can be much more effective than the existing ones.