{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T03:42:50Z","timestamp":1768794170823,"version":"3.49.0"},"reference-count":47,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1830254, 1934884"],"award-info":[{"award-number":["1830254, 1934884"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/axioms11030106","type":"journal-article","created":{"date-parts":[[2022,2,27]],"date-time":"2022-02-27T20:46:17Z","timestamp":1645994777000},"page":"106","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection"],"prefix":"10.3390","volume":"11","author":[{"given":"Fritz","family":"Keinert","sequence":"first","affiliation":[{"name":"Department of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9153-8089","authenticated-orcid":false,"given":"Eric S.","family":"Weber","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,26]]},"reference":[{"key":"ref_1","first-page":"355","article-title":"Angen\u00e4herte Aufl\u00f6sung von Systemen linearer Gleichungen","volume":"35","author":"Kaczmarz","year":"1937","journal-title":"Bull. Int. Acad. Pol. Sci. Lett. Cl. Sci. Math. Nat. Ser. A Sci. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01436376","article-title":"Projection Method for Solving a Singular System of Linear Equations and its Application","volume":"17","author":"Tanabe","year":"1971","journal-title":"Numer. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0024-3795(81)90139-7","article-title":"Iterative Algorithms for Large Partitioned Linear Systems, with Applications to Image Reconstruction","volume":"40","author":"Eggermont","year":"1981","journal-title":"Linear Alg. Appl."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Natterer, F. (1986). The Mathematics of Computerized Tomography, Teubner.","DOI":"10.1007\/978-3-663-01409-6"},{"key":"ref_5","first-page":"385","article-title":"A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations","volume":"Volume 6","author":"Balan","year":"2021","journal-title":"Excursions in Harmonic Analysis"},{"key":"ref_6","unstructured":"West, D.B. (1996). Introduction to Graph Theory, Prentice Hall, Inc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-247X(78)90214-7","article-title":"The angles between the null spaces of X rays","volume":"62","author":"Hamaker","year":"1978","journal-title":"J. Math. Anal. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/s00041-008-9030-4","article-title":"A randomized Kaczmarz algorithm with exponential convergence","volume":"15","author":"Strohmer","year":"2009","journal-title":"J. Fourier Anal. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1137\/120889897","article-title":"Randomized extended Kaczmarz for solving least squares","volume":"34","author":"Zouzias","year":"2013","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.laa.2015.06.027","article-title":"Randomized block Kaczmarz method with projection for solving least squares","volume":"484","author":"Needell","year":"2015","journal-title":"Linear Algebra Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s10107-015-0864-7","article-title":"Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm","volume":"155","author":"Needell","year":"2016","journal-title":"Math. Progr."},{"key":"ref_12","unstructured":"Cimmino, G. (1938). Calcolo approssimato per soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica XVI, Series II, Anno IX 1."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/S0167-8191(00)00100-9","article-title":"Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems","volume":"27","author":"Censor","year":"2001","journal-title":"Parallel Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1425","DOI":"10.1137\/19M1251643","article-title":"Faster randomized block Kaczmarz algorithms","volume":"40","author":"Necoara","year":"2019","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s10543-020-00824-1","article-title":"Randomized Kaczmarz with averaging","volume":"61","author":"Moorman","year":"2021","journal-title":"BIT Numer. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1109\/TAC.1986.1104412","article-title":"Distributed asynchronous deterministic and stochastic gradient optimization algorithms","volume":"31","author":"Tsitsiklis","year":"1986","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.jpdc.2006.08.010","article-title":"Distributed average consensus with least-mean-square deviation","volume":"67","author":"Xiao","year":"2007","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/1300000014","article-title":"Gossip Algorithms","volume":"3","author":"Shah","year":"2008","journal-title":"Found. Trends Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","article-title":"Distributed optimization and statistical learning via the alternating direction method of multipliers","volume":"3","author":"Boyd","year":"2011","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/TAC.2008.2009515","article-title":"Distributed subgradient methods for multi-agent optimization","volume":"54","author":"Nedic","year":"2009","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1137\/08073038X","article-title":"A randomized incremental subgradient method for distributed optimization in networked systems","volume":"20","author":"Johansson","year":"2009","journal-title":"SIAM J. Optim."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1835","DOI":"10.1137\/130943170","article-title":"On the convergence of decentralized gradient descent","volume":"26","author":"Yuan","year":"2016","journal-title":"SIAM J. Optim."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1561\/2200000051","article-title":"Adaptation, learning, and optimization over networks","volume":"7","author":"Sayed","year":"2014","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhang, X., Liu, J., Zhu, Z., and Bentley, E.S. (May, January 29). Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks. Proceedings of the IEEE INFOCOM 2019\u2014IEEE Conference on Computer Communications, Paris, France.","DOI":"10.1109\/INFOCOM.2019.8737489"},{"key":"ref_25","unstructured":"Scaman, K., Bach, F., Bubeck, S., Massouli\u00e9, L., and Lee, Y.T. (2018, January 3\u20138). Optimal algorithms for non-smooth distributed optimization in networks. Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada."},{"key":"ref_26","unstructured":"Loizou, N., and Richt\u00e1rik, P. (2019). Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols. arXiv."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s10957-016-1058-z","article-title":"Random block coordinate descent methods for linearly constrained optimization over networks","volume":"173","author":"Necoara","year":"2017","journal-title":"J. Optim. Theory Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s10107-018-1232-1","article-title":"Linear convergence of first order methods for non-strongly convex optimization","volume":"175","author":"Necoara","year":"2019","journal-title":"Math. Progr."},{"key":"ref_29","unstructured":"Bertsekas, D.P., and Tsitsiklis, J.N. (1997). Parallel and Distributed Computation: Numerical Methods, Athena Scientific. Available online: http:\/\/hdl.handle.net\/1721.1\/3719."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Kamath, G., Ramanan, P., and Song, W.Z. (2015, January 10\u201312). Distributed Randomized Kaczmarz and Applications to Seismic Imaging in Sensor Network. Proceedings of the 2015 International Conference on Distributed Computing in Sensor Systems, Fortaleza, Brazil.","DOI":"10.1109\/DCOSS.2015.27"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/S0019-9958(79)90160-8","article-title":"On the Bayesian approach to image reconstruction","volume":"42","author":"Herman","year":"1979","journal-title":"Inform. Control"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Hansen, P.C. (2010). Discrete Inverse Problems: Insight and Algorithms, Society for Industrial and Applied Mathematics (SIAM). Fundamentals of Algorithms.","DOI":"10.1137\/1.9780898718836"},{"key":"ref_33","unstructured":"Liu, J., Wright, S.J., and Sridhar, S. (2014). An asynchronous parallel randomized Kaczmarz algorithm. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1093\/imamat\/25.4.361","article-title":"A storage-efficient algorithm for finding the regularized solution of a large, inconsistent system of equations","volume":"25","author":"Herman","year":"1980","journal-title":"J. Inst. Math. Appl."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1109\/LSP.2016.2590468","article-title":"Kaczmarz method for solving quadratic equations","volume":"23","author":"Chi","year":"2016","journal-title":"IEEE Signal Process. Lett."},{"key":"ref_36","first-page":"345","article-title":"Finding common fixed points of strict paracontractions by averaging strings of sequential iterations","volume":"3","author":"Crombez","year":"2002","journal-title":"J. Nonlinear Convex Anal."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1081\/NFA-120003670","article-title":"Parallel algorithms for finding common fixed points of paracontractions","volume":"23","author":"Crombez","year":"2002","journal-title":"Numer. Funct. Anal. Optim."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1080\/10556788.2016.1209500","article-title":"Convergence of string-averaging method for a class of operators","volume":"31","author":"Nikazad","year":"2016","journal-title":"Optim. Methods Softw."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s11075-015-0045-z","article-title":"A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in Hilbert space","volume":"72","author":"Reich","year":"2016","journal-title":"Numer. Algorithms"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10589-012-9491-x","article-title":"Convergence and perturbation resilience of dynamic string-averaging projection methods","volume":"54","author":"Censor","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"ref_41","first-page":"623","article-title":"Dynamic string-averaging projection methods for convex feasibility problems in the presence of computational errors","volume":"15","author":"Zaslavski","year":"2014","journal-title":"J. Nonlinear Convex Anal."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Witt, M., Schultze, B., Schulte, R., Schubert, K., and Gomez, E. (November, January 27). A proton simulator for testing implementations of proton CT reconstruction algorithms on GPGPU clusters. Proceedings of the 2012 IEEE Nuclear Science Symposium and Medical Imaging Conference Record (NSS\/MIC), Anaheim, CA, USA.","DOI":"10.1109\/NSSMIC.2012.6551986"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/s13663-021-00694-4","article-title":"String-averaging methods for best approximation to common fixed point sets of operators: The finite and infinite cases","volume":"21","author":"Censor","year":"2021","journal-title":"Fixed Point Theory Algorithms Sci. Eng."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1080\/10556780310001610484","article-title":"Convergence of string-averaging projection schemes for inconsistent convex feasibility problems","volume":"18","author":"Censor","year":"2003","journal-title":"Optim. Methods Softw."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Haddock, J., and Needell, D. (2017, January 25\u201330). Randomized projections for corrupted linear systems. Proceedings of the AIP Conference Proceedings, Thessaloniki, Greece.","DOI":"10.1063\/1.5044141"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/j.laa.2020.10.035","article-title":"Accelerating the distributed Kaczmarz algorithm by strong over-relaxation","volume":"611","author":"Borgard","year":"2021","journal-title":"Linear Algebra Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s10543-010-0265-5","article-title":"Randomized Kaczmarz solver for noisy linear systems","volume":"50","author":"Needell","year":"2010","journal-title":"BIT"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/3\/106\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:28:20Z","timestamp":1760135300000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/3\/106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,26]]},"references-count":47,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["axioms11030106"],"URL":"https:\/\/doi.org\/10.3390\/axioms11030106","relation":{},"ISSN":["2075-1680"],"issn-type":[{"value":"2075-1680","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,26]]}}}