On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems

To enhance the computational performance of the partially randomized extended Kaczmarz (PREK) method, we propose the multi-step PREK (MPREK) method. By iteratively updating at each step, we establish a non-smooth inner-outer iteration scheme to solve the large, sparse, and inconsistent linear systems. For the MPREK method, a proof of its convergence and an upper bound on the convergence rate are given. Moreover, we show that this upper bound can be lower than that of the PREK method and the multi-step randomized extended Kaczmarz (MREK) method for certain typical choices of the inner iteration step size. Numerical experiments also indicate that, for an appropriate choice of the number of inner iteration steps, the MPREK method has a more efficient computational performance.