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 .
A distributed version of the Kaczmarz algorithm was introduced in @cite_20 . The main ideas presented there are very similar to ours: updated estimates are obtained from prior estimates using the Kaczmarz update with the equations that are available at the node, and distributed estimates are averaged together at a single node (which the authors refer to as a fusion center, for us it is the root of the tree). In @cite_20 , the convergence analysis is limited to the case of consistent systems of equations, and inconsistent systems are handled by Tikhonov regularization @cite_17 @cite_26 rather than by varying the relaxation parameter.
@cite_26 @cite_20 @cite_17
1496894444 2083268403
Many real-world wireless sensor network applications such as environmental monitoring, structural health monitoring, and smart grid can be formulated as a least-squares problem. In distributed Cyber-Physical System (CPS), each sensor node observes partial phenomena due to spatial and temporal restriction and is able to form only partial rows of least-squares. Traditionally, these partial measurements were gathered at a centralized location. However, with the increase in sensors and their measurements, aggregation is becoming challenging and infeasible. In this paper, we propose distributed randomized kaczmarz that performs in-network computation to solve least-squares over the network by avoiding costly communication. As a case study, we present a volcano monitoring application on a distributed CORE emulator and use real data from Mt. St. Helens to evaluate our proposed method. A new iterative method is proposed for finding the optimal Bayesian estimate of an unknown image from its projection data (experimentally obtained integrals of its grayness over thin strips). Convergence of the method is proved and its performance is illustrated. The method compares favorably with previously proposed procedures.