Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

DOI10.1016/J.LAA.2020.10.035zbMATH Open1473.65034arXiv2006.01739OpenAlexW3096622089MaRDI QIDQ2228508FDOQ2228508

Authors: Riley Borgard, Haley Duba, Chloe Makdad, Randal Tuggle, Steven N. Harding, Jay P. Mayfield, Eric S. Weber 

Publication date: 17 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kazmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.

Full work available at URL: https://arxiv.org/abs/2006.01739

Recommendations

• Faster randomized block Kaczmarz algorithms
• A new greedy Kaczmarz algorithm for the solution of very large linear systems
• An accelerated randomized Kaczmarz algorithm
• Kaczmarz algorithm with relaxation in Hilbert space
• An accelerated randomized Kaczmarz method via low-rank approximation

zbMATH Keywords

distributed algorithmKaczmarz algorithmlinear systems of equations

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Linear equations (linear algebraic aspects) (15A06) Iterative numerical methods for linear systems (65F10)

Cites Work

• A randomized Kaczmarz algorithm with exponential convergence
• The mathematics of computerized tomography
• Matrix theory. Basic results and techniques
• A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Projection method for solving a singular system of linear equations and its applications
• Randomized extended Kaczmarz for solving least squares
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Gossip algorithms
• Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems
• The angles between the null spaces of X rays
• Randomized block Kaczmarz method with projection for solving least squares
• A Storage-Efficient Algorithm for Finding the Regularized Solution of a Large, Inconsistent System of Equations
• The Kaczmarz algorithm, row action methods, and statistical learning algorithms
• Faster randomized block Kaczmarz algorithms

This page was built for publication: Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228508)