On greedy randomized block Gauss–Seidel method with averaging for sparse linear least-squares problems

This paper presents a greedy randomized average block sampling Gauss–Seidel (GRABGS) method for solving sparse linear least-squares problems. The GRABGS method utilizes a novel probability criterion to collect the control index set of coordinates, and minimizes the quadratic convex objective by performing multiple accurate line searches on average per iteration. The probability criterion aims to capture subvectors whose norms are relatively large. Additionly, the GRABGS method is categorized as a member of randomized block Gauss–Seidel methods, which can be employed for parallel implementations. The convergence analysis encompasses two types of extrapolation stepsizes: constant and adaptive. It is proved that the GRABGS method converges to the unique solution of the sparse linear least-squares problem when the matrix has full column rank. Numerical examples demonstrate the superiority of this method over the greedy randomized coordinate descent method and several existing state-of-the-art block Gauss–Seidel methods.