A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection
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 mo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/11/3/106 |
| _version_ | 1797447190864461824 |
|---|---|
| author | Fritz Keinert Eric S. Weber |
| author_facet | Fritz Keinert Eric S. Weber |
| author_sort | Fritz Keinert |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T13:51:21Z |
| format | Article |
| id | doaj.art-a684dc8ea76b4bd084333175b83b6005 |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-09T13:51:21Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-a684dc8ea76b4bd084333175b83b60052023-11-30T20:49:58ZengMDPI AGAxioms2075-16802022-02-0111310610.3390/axioms11030106A Randomized Distributed Kaczmarz Algorithm and Anomaly DetectionFritz Keinert0Eric S. Weber1Department of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, USADepartment of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, USAThe 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.https://www.mdpi.com/2075-1680/11/3/106Kaczmarz methodlinear equationsrandom controldistributed optimizationstochastic gradient descentsparse noise |
| spellingShingle | Fritz Keinert Eric S. Weber A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection Axioms Kaczmarz method linear equations random control distributed optimization stochastic gradient descent sparse noise |
| title | A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection |
| title_full | A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection |
| title_fullStr | A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection |
| title_full_unstemmed | A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection |
| title_short | A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection |
| title_sort | randomized distributed kaczmarz algorithm and anomaly detection |
| topic | Kaczmarz method linear equations random control distributed optimization stochastic gradient descent sparse noise |
| url | https://www.mdpi.com/2075-1680/11/3/106 |
| work_keys_str_mv | AT fritzkeinert arandomizeddistributedkaczmarzalgorithmandanomalydetection AT ericsweber arandomizeddistributedkaczmarzalgorithmandanomalydetection AT fritzkeinert randomizeddistributedkaczmarzalgorithmandanomalydetection AT ericsweber randomizeddistributedkaczmarzalgorithmandanomalydetection |