A federated Kaczmarz algorithm
In this paper, the authors introduce a federated variant of the randomized Kaczmarz method for solving distributed linear systems. In contrast to the standard federated averaging paradigm, the proposed algorithm aggregates local information through randomized projection steps motivated by the geometric interpretation of the classical Kaczmarz method [\textit{S. Kaczmarz}, Bull. Intern. Acad. Polonaise Sci. Lett., Cl. Sci. Math. Nat. A, 355--357 (1937; JFM 63.0524.02)]. Linear convergence is established for consistent systems under different communication scenarios and the analysis also yields an alternative proof of the convergence of the randomized Kaczmarz algorithm of [\textit{T. Strohmer} and \textit{R. Vershynin}, J. Fourier Anal. Appl. 15, No. 2, 262--278 (2009; Zbl 1169.68052)]. The paper also discusses extensions to underdetermined and inconsistent systems, sparse approximation via hard thresholding, and feature selection in a federated setting, illustrated by numerical experiments. The work combines ideas from federated optimization with projection methods to develop a distributed algorithm for linear systems.
- A randomized Kaczmarz algorithm with exponential convergence
- Angenäherte Auflösung von Systemen linearer Gleichungen.
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Iterative hard thresholding based on randomized Kaczmarz method
- Iterative thresholding for sparse approximations
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz in adversarial distributed setting
- Randomized Kaczmarz solver for noisy linear systems
- The Elements of Statistical Learning
This page was built for publication: A federated Kaczmarz algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7290761)
