Kaczmarz Iterative Projection and Nonuniform Sampling with Complexity Estimates

Kaczmarz’s alternating projection method has been widely used for solving mostly over-determined linear system of equations in various fields of engineering, medical imaging, and computational science. Because of its simple iterative nature with light computation, this method was successfully applied in computerized tomography. Since tomography generates a matrix with highly coherent rows, randomized Kaczmarz algorithm is expected to provide faster convergence as it picks a row for each iteration at random, based on a certain probability distribution. Since Kaczmarz’s method is a subspace projection method, the convergence rate for simple Kaczmarz algorithm was developed in terms of subspace angles. This paper provides analyses of simple and randomized Kaczmarz algorithms and explains the link between them. New versions of randomization are proposed that may speed up convergence in the presence of nonuniform sampling, which is common in tomography applications. It is anticipated that proper understanding of sampling and coherence with respect to convergence and noise can improve future systems to reduce the cumulative radiation exposures to the patient. Quantitative simulations of convergence rates and relative algorithm benchmarks have been produced to illustrate the effects of measurement coherency and algorithm performance, respectively, under various conditions in a real-time kernel. 1. Introduction Kaczmarz (in [1]) introduced an iterative algorithm for solving a consistent linear system of equations with . This method projects the estimate onto a subspace normal to the row at step cyclically with . The block Kaczmarz algorithm first groups the rows into matrices and then it projects the estimate onto the subspace normal to the subspace spanned by the rows of at step cyclically with . Obviously, the block Kaczmarz is equivalent to the simple Kaczmarz for . The Kaczmarz method is a method of alternating projection (MAP) and it has been widely used in medical imaging as an algebraic reconstruction technique (ART) [2, 3] due to its simplicity and light computation. Strohmer and Vershynin [4] proved that if a row for each iteration is picked in a random fashion with probability proportional with norm of that row, then the algorithm converges in expectation exponentially with a rate that depends on a scaled condition number of (not on the number of equations). Needell (in [5]) extended the work of [4] for noisy linear systems and developed a bound for convergence to the least square solution for . Needell also developed a randomized Kaczmarz method that