The exponential convergence rate of Kaczmarz’s algorithm and an acceleration strategy for ART

摘要

Kaczmarz’s algorithm is an iterative method for solving linear system. Generally, its convergence is considered slow. In the first part of this work, the convergence rates of Kaczmarz’s algorithm with a given default order and a random order are studied by using the abstract theorems for the convergence rate of linear operator sequences. It is proved that Kaczmarz’s algorithm always converges exponentially in both cases of the selected order, which is quite different from the slow behavior in practice, such as in image reconstruction. That means there is a remarkable gap between the theoretical rate and the actual rate. The second part of this work is to propose a new scheme with the reordered rays in each view to accelerate the practical Kaczmarz’s algorithm, i.e., the algebraic reconstruction technique (ART) in image reconstruction. Numerical experiments show that our acceleration scheme has a better performance than the previous multilevel and random-order schemes in literature.