Single projection Kaczmarz extended algorithms
From MaRDI portal
Abstract: To find the least squares solution of a very large and inconsistent system of equations, one can employ the extended Kaczmarz algorithm. This method simultaneously removes the error term, such that a consistent system is asymptotically obtained, and applies Kaczmarz iterations for the current approximation of this system. For random corrections of the right hand side and Kaczmarz updates selected at random, convergence to the least squares solution has been shown. We consider the deterministic control strategies, and show convergence to a least squares solution when row and column updates are chosen according to the almost-cyclic or maximal-residual choice.
The extended Kaczmarz algorithm provides a tool for searching the least squares solution of a large inconsistent system of equations. It is known that the original Kaczmarz method does not converge to the least squares solution in the inconsistent case. The extended version of the Kaczmarz algorithm adds a correction step in the form of an orthogonal projection on the \(i\)-th hyperplane. When the projection indices are selected at random, the so-called randomized extended Kaczmarz algorithm converges in expectation to the minimal norm solution and convergence rates can be obtained. The presented paper introduces two deterministic control schemes, the maximal-residual and the almost cyclic control scheme and shows convergence to the least squares solution.
Recommendations
- Randomized extended Kaczmarz for solving least squares
- A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems
- Randomized double and triple Kaczmarz for solving extended normal equations
- Randomized extended average block Kaczmarz for solving least squares
- Randomized block Kaczmarz method with projection for solving least squares
Cites work
- A randomized Kaczmarz algorithm with exponential convergence
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- scientific article; zbMATH DE number 1382772 (Why is no real title available?)
- scientific article; zbMATH DE number 3229228 (Why is no real title available?)
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- Least-squares solution of overdetermined inconsistent linear systems using kaczmarz's relaxation
- On Projection Algorithms for Solving Convex Feasibility Problems
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Projection method for solving a singular system of linear equations and its applications
- Quasi-Fejérian analysis of some optimization algorithms
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- Relaxation methods for image reconstruction
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- The method of projections for finding the common point of convex sets
Cited in
(39)- A new greedy Kaczmarz algorithm for the solution of very large linear systems
- On Motzkin's method for inconsistent linear systems
- Randomized double and triple Kaczmarz for solving extended normal equations
- Randomized Kaczmarz for tensor linear systems
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- A note on convergence rate of randomized Kaczmarz method
- Enhancement of the Kaczmarz algorithm with projection adjustment
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- On the error estimate of the randomized double block Kaczmarz method
- Projected randomized Kaczmarz methods
- The dual Kaczmarz algorithm
- Convergence rates for Kaczmarz-type algorithms
- On extended Kaczmarz methods with random sampling and maximum-distance for solving large inconsistent linear systems
- Randomized extended Kaczmarz for solving least squares
- Kaczmarz extended versus augmented system solution in image reconstruction
- Kaczmarz's algorithm -- extensions and preconditioning
- scientific article; zbMATH DE number 1271381 (Why is no real title available?)
- A stochastic Kaczmarz algorithm for network tomography
- 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
- The Cimmino-Kaczmarz equivalence and related results
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Randomized extended average block Kaczmarz for solving least squares
- A note on Kaczmarz algorithm with remotest set control sequence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- Randomized Kaczmarz in adversarial distributed setting
- Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications
- On multi-step extended maximum residual Kaczmarz method for solving large inconsistent linear systems
- Average block column action methods for solving least squares problems
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- Reflective block Kaczmarz algorithms for least squares
- Research on Kaczmarz algorithm based on residual drive
- On a deterministic block Kaczmarz-type method and its acceleration for the solution of large-scale linear systems
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
This page was built for publication: Single projection Kaczmarz extended algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342879)
