A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility
- Author(s): De Loera, Jesus;
- Haddock, Jamie;
- Needell, Deanna
- et al.
Published Web Locationhttps://arxiv.org/pdf/1605.01418.pdf
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.