Abstract: When iteratively solving linear systems By=b with Hermitian positive semi-definite , and in particular when solving least-squares problems for by reformulating them as , it is often observed that SOR-type methods (Gauss-Seidel, Kaczmarz) perform suboptimally for the given equation ordering, and that random reordering improves the situation on average.This paper is an attempt to provide some additional theoretical support for this phenomenon. We show eerror bounds for two randomized versions, called shuffled and preshuffled SOR, that improve asymptotically upon the best known bounds fro SOR with cyclic ordering. Our results are based on studying the behavior of the triangular truncation of Hermitian matrices with respect to their permutations.
Recommendations
- A fast randomized algorithm for overdetermined linear least-squares regression
- A generalized successive overrelaxation method for least squares problems
- Randomized extended Kaczmarz for solving least squares
- Faster least squares approximation
- Correction to: ``Random reordering in SOR-type methods
- A sufficient and necessary condition of the convergence of the SAOR iterative method for consistently ordered matrices
- The convergence of the two-block SAOR method for least-squares problems
- A Randomized Solver for Linear Systems with Exponential Convergence
- A fast randomized algorithm for orthogonal projection
- On the convergence rate of SOR: A worst case estimate
Cites work
- scientific article; zbMATH DE number 3706628 (Why is no real title available?)
- scientific article; zbMATH DE number 41508 (Why is no real title available?)
- scientific article; zbMATH DE number 1082090 (Why is no real title available?)
- A randomized Kaczmarz algorithm with exponential convergence
- Consequences of the Marcus/Spielman/Srivastava solution of the Kadison-Singer problem
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Coordinate descent algorithms
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- Iterative Methods for Solving Partial Difference Equations of Elliptic Type
- Iterative solution of large sparse systems of equations. Transl. from the German
- On the convergence rate of SOR: A worst case estimate
- Orderings of the successive overrelaxation scheme
- The Hadamard Operator Norm of a Circulant and Applications
Cited in
(10)- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Randomness and permutations in coordinate descent methods
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Properties and applications of a conjugate transform on Schatten classes
- A linear algebra perspective on the random multi-block ADMM: the QP case
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Sampling discretization and related problems
- Correction to: ``Random reordering in SOR-type methods
- On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems
This page was built for publication: Random reordering in SOR-type methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522242)
