Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem

Understand

The Sampling Kaczmarz Motzkin (SKM) algorithm is a generalized method for solving large scale linear systems of inequalities.

• Having its root in the relaxation method of Agmon, Schoenberg, and Motzkin and the randomized Kaczmarz method, SKM outperforms the state of the art methods in solving large-scale Linear Feasibility (LF) problems.
• Motivated by SKM's success, in this work, we propose an Accelerated Sampling Kaczmarz Motzkin (ASKM) algorithm which achieves better convergence compared to the standard SKM algorithm on ill conditioned problems.
• We provide a thorough convergence analysis for the proposed accelerated algorithm and validate the results with various numerical experiments.