On greedy multi-step inertial randomized Kaczmarz method for solving linear systems.

The multi-step inertial randomized Kaczmarz (MIRK) method is an iterative method for solving large-scale linear systems. In this paper, we enhance the MIRK method by incorporating the greedy probability criterion, coupled with the introduction of a tighter threshold parameter for this criterion. We prove that the proposed greedy MIRK (GMIRK) method enjoys an improved deterministic linear convergence compared to both the MIRK method and the greedy randomized Kaczmarz method. Furthermore, we exhibit that the multi-step inertial extrapolation approach can be geometrically interpreted as an orthogonal projection method, and establish its relationship with the sketch-and-project method in Gower and Richtárik (SIAM J Matrix Anal Appl 36(4):1660–1690, 2015) and the oblique projection technique in Li et al. (Results Appl. Math. 16:100342, 2022). Numerical experiments are provided to confirm our results. [ABSTRACT FROM AUTHOR]