The equivalence of the randomized extended Gauss–Seidel and randomized extended Kaczmarz methods

The randomized Kaczmarz method, the randomized Gauss-Seidel method, the randomized extended Kaczmarz method, and the randomized extended Gauss-Seidel method are four efficient randomized iteration methods for solving large-scale systems of linear equations. In this paper, we point out that the randomized extended Gauss-Seidel method is actually mathematically equivalent to the randomized extended Kaczmarz method, and we find the intrinsic connection between the randomized-Kaczmarz-type methods and the randomized-Gauss-Seidel-type methods. In addition, by classifying a linear system into four cases according to its consistency and the column-rank of its coefficient matrix, we give the preferred method among the four randomized iteration methods in each case. With these results, we can make full use of the most appropriate randomized iteration method to solve the linear system. What is more, we can also obtain new efficient randomized iteration methods based on these analyses.