  The recently proposed Sampling Kaczmarz Motzkin (SKM) algorithm performs well
in comparison with the state-of-the-art methods in solving large-scale Linear
Feasibility (LF) problems. To explore the concept of momentum in the context of
solving LF problems, in this work, we propose a momentum induced algorithm
called Momentum Sampling Kaczmarz Motzkin (MSKM). The MSKM algorithm is
developed by integrating the heavy ball momentum to the SKM algorithm. We
provide a rigorous convergence analysis of the proposed MSKM algorithm from
which we obtain convergence results of several Kaczmarz type methods for
solving LF problems. Moreover, under somewhat weaker conditions, we establish a
sub-linear convergence rate for the so-called Cesaro average of the sequence
generated by the MSKM algorithm. We then back up the theoretical results via
thorough numerical experiments on artificial and real datasets. For a fair
comparison, we test our proposed method in comparison with the SKM method on a
wide variety of test instances: 1) randomly generated instances, 2) Netlib LPs
and 3) linear classification test instances. We also compare the proposed
method with the traditional Interior Point Method (IPM) and Active Set Method
(ASM) on Netlib LPs. The proposed momentum induced algorithm significantly
outperforms the basic SKM method (with no momentum) on all of the considered
test instances. Furthermore, the proposed algorithm also performs well in
comparison with IPM and ASM algorithms. Finally, we propose a stochastic
version of the MSKM algorithm called Stochastic-Momentum Sampling Kaczmarz
Motzkin (SSKM) to better handle large-scale real-world data. We conclude our
work with a rigorous theoretical convergence analysis of the proposed SSKM
algorithm.
