On Randomized Average Block Gauss-Seidel Method and Its Greedy Version for Inconsistent Factorized Linear System

Abstract

For solving inconsistent factorized linear systems, the Randomized Gauss Seidel-Randomized Kaczmarz (RGS-RK) method is very effective. In order to improve its convergence, we first develop the randomized average block Gauss-Seidel method. Then, a simple block version of the RGS-RK method is proposed. By combining the sketching technique with greedy strategy, we present a Greedy Block version of the RGS-RK (GBRGS-RK) method. In addition, the convergence rates of the presented methods are analyzed. Several numerical examples from Phillips's problem, The University of California, Irvine machine learning datasets to random matrices are given to demonstrate that the proposed algorithms perform better in computing cost and iteration. In particular, the GBRGS-RK method secures excellent computational efficiency, which renders it extremely appropriate for large-scale inconsistent factorized linear system.