Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration

Understand

Randomized Kaczmarz (RK), Motzkin Method (MM) and Sampling Kaczmarz Motzkin (SKM) algorithms are commonly used iterative techniques for solving a system of linear inequalities (i.e., $Ax \leq b$).

• As linear systems of equations represent a modeling paradigm for solving many optimization problems, these randomized and iterative techniques are gaining popularity among researchers in different domains.
• In this work, we propose a Generalized Sampling Kaczmarz Motzkin (GSKM) method that unifies the iterative methods into a single framework.
• In addition to the general framework, we propose a Nesterov type acceleration scheme in the SKM method called as Probably Accelerated Sampling Kaczmarz Motzkin (PASKM).