Return to search

Paving the Randomized Gauss-Seidel

The Randomized Gauss-Seidel Method (RGS) is an iterative algorithm that solves overdetermined systems of linear equations Ax = b. This paper studies an update on the RGS method, the Randomized Block Gauss-Seidel Method. At each step, the algorithm greedily minimizes the objective function L(x) = kAx bk2 with respect to a subset of coordinates. This paper describes a Randomized Block Gauss-Seidel Method (RBGS) which uses a randomized control method to choose a subset at each step. This algorithm is the first block RGS method with an expected linear convergence rate which can be described by the properties of the matrix A and its column submatrices. The analysis demonstrates that RBGS improves RGS more when given appropriate column-paving of the matrix, a partition of the columns into well-conditioned blocks. The main result yields a RBGS method that is more e cient than the simple RGS method.

Identiferoai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:scripps_theses-2025
Date01 January 2017
CreatorsWu, Wei
PublisherScholarship @ Claremont
Source SetsClaremont Colleges
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceScripps Senior Theses
Rights© 2017 Wei Wu, default

Page generated in 0.0017 seconds