A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
Jesús A. De Loera, Jamie Haddock, Deanna Needell · SIAM Journal on Scientific Computing · 2017
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. We obtain a family of algorithms that generalize and extend both projection-based techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.