A Semi-randomized Block Kaczmarz Method with Simple Random Sampling for Large-Scale Consistent Linear Systems

The randomized block Kaczmarz (RBK) method is a randomized orthogonal projection iterative approach, which plays an important role in solving large-scale linear systems. A key point of this type of method is to select working rows effectively during iterations. However, in most of the RBK-type methods, one has to scan all the rows of the coefficient matrix in advance to compute probabilities or paving, or to compute the residual vector of the linear system in each iteration to determine the working rows. These are unfavorable for big data problems. To cure these drawbacks, we propose a semi-randomized block Kaczmarz (SRBK) method with simple random sampling for large-scale linear systems in this paper. The convergence of the proposed method is established. Numerical experiments on some real-world and large-scale data sets show that the proposed method is often superior to many state-of-the-art RBK-type methods for large linear systems.