A Greedy Gauss-Seidel Method for Solving the Large Linear Least Squares Problem

Abstract:

An alternative greedy Gauss-Seidel method for solving the large linear least squares problem is proposed based on a novel strategy for choosing the working columns of the coefficient matrix A， and the convergence of the new method is analyzed. The numerical experiments show that for the same accuracy， the method proposed in this paper outperforms the greedy randomized coordinate descent method proposed recently in term of the computing time.

Key words:greedy Gauss-Seidel method;greedy randomized coordinate descent method;randomized Gauss-Seidel method;large linear least squares problem