The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations Ax=b. The randomized version of the Kaczmarz method put forth by Strohmer and Vershynin iteratively projects onto a randomly chosen solution space given by a single row of the matrix A and converges exponentially in expectation to the solution of a consistent system. In this paper we analyze two block versions of the method each with a randomized projection, that converge in expectation to the least squares solution of inconsistent systems. Our approach utilizes a paving of the matrix A to guarantee exponential convergence, and suggests that paving yields a significant improvement in performance in certain regimes. The proposed method is an extension of the block Kaczmarz method analyzed by Needell and Tropp and the Randomized Extended Kaczmarz method of Zouzias and Freris. The contribution is thus two-fold; unlike the standard Kaczmarz method, our methods converge to the least-squares solution of inconsistent systems, and by using appropriate blocks of the matrix this convergence can be significantly accelerated. Numerical experiments suggest that the proposed algorithm can indeed lead to advantages in practice.
@cite_38: Abstract In this paper we construct and theoretically analyze a class of direct projection algorithms for the numerical solution of linear least squares problems. These algorithms are obtained by adding supplementary directions for projection, constructed as linear combinations of the initial system rows and columns, in Kaczmarz and Extended Kaczmarz iterative methods. The above ideas are extended to the block row and column versions of the previously mentioned methods. The developed algorithms are then compared with other direct projection-based methods by the application to problems arising in multibody elasticity.
@cite_22: The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax?=?b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson---Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.
@cite_29: The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.
@cite_52: 
@cite_32: Applied Iterative Methods is a self-contained treatise suitable as both a reference and a graduate-level textbook in the area of iterative algorithms. It is the first book to combine subjects such as optimization, convex analysis, and approximation theory and organize them around a detailed and mathematically sound treatment of iterative algorithms. Such algorithms are used in solving problems in a diverse area of applications, most notably in medical imaging such as emission and transmission tomography and magnetic-resonance imaging, as well as in intensity-modulated radiation therapy. Other applications, which lie outside of medicine, are remote sensing and hyperspectral imaging. This book details a great number of different iterative algorithms that are universally applicable.
@cite_44: Abstract We present a unifying framework for a wide class of iterative methods in numerical linear algebra. In particular, the class of algorithms contains Kaczmarz's and Richardson's methods for the regularized weighted least squares problem with weighted norm. The convergence theory for this class of algorithms yields as corollaries the usual convergence conditions for Kaczmarz's and Richardson's methods. The algorithms in the class may be characterized as being group-iterative, and incorporate relaxation matrices, as opposed to a single relaxation parameter. We show that some well-known iterative methods of image reconstruction fall into the class of algorithms under consideration, and are thus covered by the convergence theory. We also describe a novel application to truly three-dimensional image reconstruction.
@cite_15: We shall in this paper consider the problem of computing a generalized solution of a given linear system of equations. The matrix will be partitioned by blocks of rows or blocks of columns. The generalized inverses of the blocks are then used as data to Jacobi- and SOR-types of iterative schemes. It is shown that the methods based on partitioning by rows converge towards the minimum norm solution of a consistent linear system. The column methods converge towards a least squares solution of a given system. For the case with two blocks explicit expressions for the optimal values of the iteration parameters are obtained. Finally an application is given to the linear system that arises from reconstruction of a two-dimensional object by its one-dimensional projections.
@cite_17: 
Another important aspect of research in this area focuses on accelerating the convergence of the methods. Geometric brute force methods can be used @cite_22 , additional row directions may be added @cite_38 , or instead one can select of rows rather than a single row in each iteration. The block version of the Kaczmarz method is originally due to work of Elfving @cite_15 and @cite_44 . Its convergence rates were recently studied in @cite_17 and analyzed via pavings by Needell and Tropp @cite_29 . The block Kaczmarz method is of course a special instance in a broader class of block projection algorithms, see for example @cite_52 for a more general analysis and @cite_32 for a presentation of other block variants.