A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection
A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection
复制标题
DOI：
10.3390/axioms11030106
复制
发表时间：
2022-02
期刊：
影响因子：
2
通讯作者：
F. Keinert;Eric S. Weber
中科院分区：
文献类型：
--
作者：
F. Keinert;Eric S. Weber
Kaczmarz算法是一种解线性方程组的迭代方法。介绍了一种在分布式环境下求解线性方程组的随机Kaczmarz算法，即系统中的方程分布在网络中的多个节点上。我们引入的修改是为具有树结构的网络设计的，该结构允许在网络中的节点之间传递解估计。当系统相容时，我们证明了算法收敛于最小范数解。我们还证明了随机算法的收敛速度依赖于系数矩阵的谱数据和随机控制概率分布。此外，我们还证明了当测量受到大的稀疏噪声扰动时，可以使用随机化算法来识别方程组中的异常。
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.