A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems

Abstract

A two-step randomized Gauss-Seidel (TRGS) method is presented for large linear least squares problem with tall and narrow coefficient matrix. The TRGS method projects the approximate solution onto the solution space by given two random columns and is proved to be convergent when the coefficient matrix is of full rank. Several numerical examples show the effectiveness of the TRGS method among all methods compared.

Keywords

• linear least-squares problem
• two-step iterative method
• convergence property
• gauss-seidel