# A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility

arXiv: https://arxiv.org/abs/1605.01418 · HTML: https://mlsanity.com/paper/1605.01418/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2016.

## Built on by (most cited first, 9 of 9)

- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [ORKA: Accelerated Kaczmarz Algorithms for Signal Recovery from One-Bit Samples](https://mlsanity.com/paper/2301.03467/) (2022)
- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)
- [T-SKM-Net: Trainable Neural Network Framework for Linear Constraint Satisfaction via Sampling Kaczmarz-Motzkin Method](https://mlsanity.com/paper/2512.10461/) (2025)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [k-Submodular Interdiction Problems under Distributional Risk-Receptiveness and Robustness: Application to Machine Learning](https://mlsanity.com/paper/2406.13023/) (2024)
- [GRIP: Algorithm-Agnostic Machine Unlearning for Mixture-of-Experts via Geometric Router Constraints](https://mlsanity.com/paper/2601.16905/) (2026)
- [AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs](https://mlsanity.com/paper/2609.30088/) (2026)

## Abstract (arXiv)

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.