A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility

2016/05/04 by De Loera, Jesus, Haddock, Jamie, Needell, Deanna · 5 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1605.01418

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.

Cited by

• T-SKM-Net: Trainable Neural Network Framework for Linear Constraint Satisfaction via Sampling Kaczmarz-Motzkin Method
• Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods
• Read Between the Hyperplanes: On Spectral Projection and Sampling Approaches to Randomized Kaczmarz
• Sample Abundance for Signal Processing: A Brief Introduction
• Two-dimensional greedy randomized Kaczmarz methods for solving large-scale linear systems

Related

• On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems
• Greedy Motzkin-Kaczmarz methods for solving linear systems
• Block sampling Kaczmarz-Motzkin methods for consistent linear systems
• Randomized block subsampling Kaczmarz-Motzkin method
• Block Kaczmarz Method with Inequalities