Several Randomized Algorithms Based On Randomized Gauss-Seidel Method

Based on the randomized Gauss-Seidel method for solving the least-square problem,this paper proposes three new algorithms.Firstly,we apply a greedy workspace selection strategy from GRGS algorithm to a variant RGS method for solving ridge regression least squares problem,and called it VGRGS.We also considered the version of the VGRGS method with relaxation factor,theoretical analysis and experimental data show that the new method is more effective than VRGS algorithm in solving the overdetermined system derived from ridge regression problem.In addition,we also propose two improvements to the REGS algorithm.The first is to accelerate the REGS method by using greedy column criterion to select more efficient column index in each iteration,and the second is to change the random selection of rows and columns to the random selection of only the columns of the matrix,and loop through the rows of the matrix in a given way.For these two modified schemes,we give a better upper bound of convergence then REGS algorithm in theory.It also show the feasibility and effectiveness of these two methods in our numerical experiment.