The Kaczmarz algorithm is an iterative method for solving systems of linear equations. We introduce a modified Kaczmarz algorithm for solving systems of linear equations in a distributed environment, i.e. the equations within the system are distributed over multiple nodes within a network. The modification we introduce is designed for a network with a tree structure that allows for passage of solution estimates between the nodes in the network. We prove that the modified algorithm converges under no additional assumptions on the equations. We demonstrate that the algorithm converges to the solution, or the solution of minimal norm, when the system is consistent. We also demonstrate that in the case of an inconsistent system of equations, the modified relaxed Kaczmarz algorithm converges to a weighted least squares solution as the relaxation parameter approaches @math .
The Kaczmarz method was originally introduced in ( @cite_28 , 1937). It became popular with the introduction of Computer Tomography, under the name of ART (Algebraic Reconstruction Technique). ART added non-negativity and other constraints to the standard algorithm @cite_22 . Other variations on the Kaczmarz method allowed for relaxation parameters @cite_6 , re-ordering equations to speed up convergence @cite_10 , or considering block versions of the Kaczmarz method with relaxation matrices @math @cite_8 . Relatively recently, choosing the next equation randomly has been shown to dramatically improve the rate of convergence of the algorithm @cite_0 @cite_21 @cite_3 . Moreover, this randomized version of the Kaczmarz algorithm has been shown to comparable to the gradient descent method @cite_15 . Our version of the Kaczmarz method differs from these in that the next equation cannot be chosen randomly or otherwise, since the ordering of the equations is determined by the network topology.
@cite_22 @cite_8 @cite_28 @cite_21 @cite_6 @cite_3 @cite_0 @cite_15 @cite_10
1967981081 2048305372 2036835849 1754711404
The algebraic reconstruction technique (ART), based on the well known algorithm proposed by Kaczmarz in 1937, is one of the most important class of solution methods for image reconstruction problems. But unfortunately, almost all the methods from the ART class give satisfactory results only in the case of consistent problems. In the inconsistent case (and unfortunately this is what happens in real applications, because of measurement errors) they give only more or less "controllable" versions of the exact solutions. This is exactly the case that we analyze in the present paper. We start with a theoretical analysis of the classical Kaczmarz's projection method in the case of an inconsistent linear least-squares problem and we prove that the approximations so obtained are at a certain distance from the set of exact least-squares solutions. This distance is controlled by the component of the right hand side of the problem lying in the orthogonal complement of the range of problem's matrix, i.e. exactly the component that makes the problem inconsistent. For overcoming this difficulty we consider an extended version of Kaczmarz's algorithm, previously analyzed by one of the authors. In the numerical experiments described in the last part of the paper we compare the above mentioned extension with two well known (ART) type algorithms for image reconstruction in two electromagnetic geotomography problems. The results indicate that the extended Kaczmarz algorithm gives much better results than the other two. The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of in the context of reconstructing bandlimited functions from nonuniform sampling. 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. Abstract The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations A x = 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 linearly 1 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, designed to converge in expectation to the least squares solution, often faster than the standard variants. Our approach utilizes both a row and column-paving of the matrix A to guarantee linear convergence when the matrix has consistent row norms (called nearly standardized), and a single column-paving when the row norms are unbounded. The proposed methods are 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 results demonstrate convergence to the least squares solution of inconsistent systems (both methods in the nearly standardized case and the second method in other cases). By using appropriate blocks of the matrix this convergence can be significantly accelerated, as is demonstrated by numerical experiments.