A sampling Kaczmarz-Motzkin algorithm for linear feasibility

Abstract: We combine two iterative algorithms for solving large-scale systems of linear inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method. In doing so, we obtain a family of algorithms that generalize and extend both techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.

Recommendations

Cites work

Cited in

(44)

Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
Kaczmarz method with oblique projection
Randomized extended average block Kaczmarz for solving least squares
Greedy randomized sampling nonlinear Kaczmarz methods
On greedy randomized average block Kaczmarz method for solving large linear systems
On Motzkin's method for inconsistent linear systems
Enhancement of the Kaczmarz algorithm with projection adjustment
On Adaptive Sketch-and-Project for Solving Linear Systems
Quantile-based iterative methods for corrupted systems of linear equations
Stochastic iterative methods for online rank aggregation from pairwise comparisons
On greedy randomized block Kaczmarz method for consistent linear systems
A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
On the Meany inequality with applications to convergence analysis of several row-action iteration methods
On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
On randomized multiple row-action methods for linear feasibility problems
A greedy randomized average block projection method for linear feasibility problems
Randomized methods for linear constraints: convergence rates and conditioning
Convergence analysis of the nonlinear Kaczmarz method for systems of nonlinear equations with componentwise convex mappings and applications to image reconstruction in multispectral CT
On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation A X B = C
Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
Randomized Kaczmarz algorithm with averaging and block projection
Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
On block Gaussian sketching for the Kaczmarz method
A sampling Kaczmarz-Motzkin algorithm for tensor linear systems
Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
Polyhedral Newton-min algorithms for complementarity problems
The randomized circumcentered-reflection iteration method for solving consistent linear equations
k-submodular interdiction problems under distributional risk-receptiveness and robustness: application to machine learning
Block Kaczmarz method with inequalities
Efficient randomized block Kaczmarz method for linear feasibility
On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems
Splitting-based randomized iterative methods for solving indefinite least squares problem
Randomized block subsampling Kaczmarz-Motzkin method
Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
RidgeSketch: a fast sketching based solver for large scale ridge regression
Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
Block sampling Kaczmarz-Motzkin methods for consistent linear systems
Randomized Kaczmarz for tensor linear systems

Describes a project that uses

Uses Software