On Fast Randomized and Deterministic Block Gauss‐Seidel Methods for Solving Least Squares Problems

ABSTRACT In this paper, we propose and analyze two block Gauss‐Seidel methods, one randomized and one deterministic, to solve large linear least squares problems. We prove the convergence of the proposed methods for full‐rank overdetermined systems and provide numerical experiments to show their effectiveness compared to existing methods. In contrast to other block Kaczmarz and block coordinate descent algorithms, the proposed methods are especially advantageous when it comes to their implementation.