A DETERMINISTIC KACZMARZ ALGORITHM FOR SOLVING LINEAR SYSTEMS

We propose a new deterministic Kaczmarz algorithm for solving consistent linear systems Ax = b. Basically, the algorithm replaces orthogonal projections with reflections in the original scheme of Stefan Kaczmarz. Building on this, we give a geometric description of solutions of linear systems. Suppose A is m \times n, we show that the algorithm generates a series of points distributed with patterns on an (n -1)-sphere centered on a solution. These points lie evenly on 2m lower-dimensional spheres {Sk0, Sk1}km=1, with the property that for any k, the midpoint of the centers of Sk0, Sk1 is exactly a solution of Ax = b. With this discovery, we prove that taking the average of O(eta (A) log(1/\varepsilon )) points on any Sk0 \cupSk 1 effectively approximates a solution up to relative error \varepsilon , where eta(A) characterizes the eigengap of the orthogonal matrix produced by the product of m reflections generated by the rows of A. We also analyze the connection between eta(A) and \kappa (A), the condition number of A. In the worst case eta(A) = O(\kappa2(A) log m), while for random matrices eta(A) = O(\kappa (A)) on average. Finally, we prove that the algorithm indeed solves the linear system ATW -1Ax = ATW-1b, where W is the lower-triangular matrix such that W + WT = 2AAT. The connection between this linear system and the original one is studied. The numerical tests indicate that this new Kaczmarz algorithm has comparable performance to randomized (block) Kaczmarz algorithms.