The Kaczmarz algorithm is an iterative method for solving systems of linear equations. We introduce a randomized 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 demonstrate that the algorithm converges to the solution, or the solution of minimal norm, when the system is consistent. We also prove convergence rates of the randomized algorithm that depend on the spectral data of the coefficient matrix and the random control probability distribution. In addition, we demonstrate that the randomized algorithm can be used to identify anomalies in the system of equations when the measurements are perturbed by large, sparse noise.
more »
« less
A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
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 0.
more »
« less
- Award ID(s):
- 1830254
- NSF-PAR ID:
- 10168692
- Date Published:
- Journal Name:
- Applied and numerical harmonic analysis
- ISSN:
- 2296-5009
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data areavailable at: https://github.com/bridgelessqiu/NMIN-FPEmore » « less
-
The Kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector $x$ in a (separable) Hilbert space from the inner-products $\{ \langle x, \phi_{n} \rangle \}$. The Kaczmarz algorithm defines a sequence of approximations from the sequence $\{ \langle x, \phi_{n} \rangle \}$; these approximations only converge to $x$ when $\{ \phi_{n} \}$ is \emph{effective}. We dualize the Kaczmarz algorithm so that $x$ can be obtained from $\{\langle x, \phi_{n} \rangle\}$ by using a second sequence $\{\psi_{n}\}$ in the reconstruction. This allows for the recovery of $x$ even when the sequence $\{\phi_{n}\}$ is not effective; in particular, our dualization yields a reconstruction when the sequence $\{\phi_{n}\}$ is \emph{almost effective}. We also obtain some partial results characterizing when the sequence of approximations from $\{\langle \vec{x}, \phi_{n} \rangle\}$ converges to $x$, in which case $\{ (\phi_{n}, \psi_{n}) \}$ is called an effective pair.more » « less
-
Proliferation of distributed Cyber-Physical Systems has raised the need for developing computationally efficient security solutions. Toward this objective, distributed state estimators that can withstand attacks on agents (or nodes) of the system have been developed, but many of these works consider the estimation error to asymptotically converge to zero by restricting the number of agents that can be compromised. We propose Resilient Distributed Kalman Filter (RDKF), a novel distributed algorithm that estimates states within an error bound and does not depend on the number of agents that can be compromised by an attack. Our method is based on convex optimization and performs well in practice, which we demonstrate with the help of a simulation example. We theoretically show that, in a connected network, the estimation error generated by the Distributed Kalman Filter and our RDKF at each agent converges to zero in an attack free and noise free scenario. Furthermore, our resiliency analysis result shows that the RDKF algorithm bounds the disturbance on the state estimate caused by an attack.more » « less
-
more » « less
Abstract In the context of cosmic microwave background data analysis, we study the solution to the equation that transforms scanning data into a map. As originally suggested in “messenger” methods for solving linear systems, we split the noise covariance into uniform and nonuniform parts and adjust their relative weights during the iterative solution. With simulations, we study mock instrumental data with different noise properties, and find that this “cooling” or perturbative approach is particularly effective when there is significant low-frequency noise in the timestream. In such cases, a conjugate gradient algorithm applied to this modified system converges faster and to a higher fidelity solution than the standard conjugate gradient approach. We give an analytic estimate for the parameter that controls how gradually the linear system should change during the course of the solution.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/978-3-030-69637-5_20
