On the generally randomized extended Gauss-Seidel method

The randomized extended Gauss-Seidel method is a popular representative among the iterative algorithm due to its simplicity for solving the inconsistent and consistent systems of linear equations, which builds the connection between the randomized Kaczmarz and Gauss-Seidel methods. In this work we develop a general version of the randomized extended Gauss-Seidel method, as well as some new iterative schemes. We prove that our algorithm can exponentially converge in expectation to the solutions of the consistent or inconsistent linear systems under two different sampling strategies. Numerical examples show that the proposed algorithm is feasible and effective, where the block method performs significantly better than the corresponding original form.