Inspired by Randomized Kaczmarz with Mismatched Adjoint (RKMA) proposed by Lorenz et al. [17] and the semi-randomized Kaczmarz method with simple random sampling (PRKS) proposed by Jiang et al. [12], we propose two novel randomized Kaczmarz (RK) methods with maximal residual for solving large overdetermined consistent linear systems. In the new methods, we select the row with the optimal local residuals as the working row, and, respectively, project the current solution orthogonally or obliquely onto the hyperplane formed by the working row. Under the assumption that matrix A has full column rank, we conduct a convergence analysis of the new RK methods and derive the upper bounds for their expected convergence rates. Furthermore, numerical experiments are performed to validate the superior efficiency of these methods compared to the RK, RKMA, PRKS, and the fast deterministic block Kaczmarz methods.
