On Motzkin's method for inconsistent linear systems
From MaRDI portal
Publication:1999709
Abstract: Iterative linear solvers have gained recent popularity due to their computational efficiency and low memory footprint for large-scale linear systems. The relaxation method, or Motzkin's method, can be viewed as an iterative method that projects the current estimation onto the solution hyperplane corresponding to the most violated constraint. Although this leads to an optimal selection strategy for consistent systems, for inconsistent least square problems, the strategy presents a tradeoff between convergence rate and solution accuracy. We provide a theoretical analysis that shows Motzkin's method offers an initially accelerated convergence rate and this acceleration depends on the dynamic range of the residual. We quantify this acceleration for Gaussian systems as a concrete example. Lastly, we include experimental evidence on real and synthetic systems that support the analysis.
The authors show that Motzkin's method for systems of linear equations has an initially accelerated convergence rate for residuals with a large dynamic range. Moreover they provide bounds for the iterate error in the case of full column rank matrices with normalized rows. For the particular case of Gaussian systems of linear equations the authors provide bounds on this value.
Recommendations
Cites work
- A randomized Kaczmarz algorithm with exponential convergence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Randomized extended Kaczmarz for solving least squares
- Randomized iterative methods for linear systems
- Randomized Kaczmarz solver for noisy linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Single projection Kaczmarz extended algorithms
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
Cited in
(17)- Randomized Kaczmarz for tensor linear systems
- On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation A X B = C
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- An extended row and column method for solving linear systems on a quantum computer
- On greedy randomized block Kaczmarz method for consistent linear systems
- The randomized Kaczmarz algorithm with the probability distribution depending on the angle
- Randomized block subsampling Kaczmarz-Motzkin method
- Consistent-inconsistent decomposition to initial value problem of descriptor linear systems
- A weighted randomized Kaczmarz method for solving linear systems
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Quantile-based iterative methods for corrupted systems of linear equations
- Randomized extended average block Kaczmarz for solving least squares
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- Approximate Solutions of Linear Systems at a Universal Rate
- Randomized Kaczmarz algorithm with averaging and block projection
- Greedy block extended Kaczmarz method for solving the least squares problems
This page was built for publication: On Motzkin's method for inconsistent linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1999709)
