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.
The Kaczmarz method was originally introduced in the paper @cite_23 . It was reinvented by researchers in tomography @cite_24 under the appellation algebraic reconstruction technique'' (ART). See Byrne's book @cite_36 for a contemporary summary of this literature.
@cite_24 @cite_36 @cite_23
1990919278 625703071
Abstract We give a new method for direct reconstruction of three-dimensional objects from a few electron micrographs taken at angles which need not exceed a range of 60 degrees. The method works for totally asymmetric objects, and requires little computer time or storage. It is also applicable to X-ray photography, and may greatly reduce the exposure compared to current methods of body-section radiography. 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.