Exponential convergence of a distributed algorithm for solving linear algebraic equations

DOI10.1016/J.AUTOMATICA.2017.05.004zbMATH Open1373.93022arXiv1701.00554OpenAlexW2584178556WikidataQ115583306 ScholiaQ115583306MaRDI QIDQ1679072FDOQ1679072

Authors: Ji Liu, A. Stephen Morse, Angelia Nedić, Tamer Başar 

Publication date: 8 November 2017

Published in: Automatica (Search for Journal in Brave)

Abstract: In a recent paper, a distributed algorithm was proposed for solving linear algebraic equations of the form $Ax=b$ assuming that the equation has at least one solution. The equation is presumed to be solved by $m$ agents assuming that each agent knows a subset of the rows of the matrix $[A;b]$, the current estimates of the equation's solution generated by each of its neighbors, and nothing more. Neighbor relationships are represented by a time-dependent directed graph $N(t)$ whose vertices correspond to agents and whose arcs characterize neighbor relationships. Sufficient conditions on $N(t)$ were derived under which the algorithm can cause all agents' estimates to converge exponentially fast to the same solution to $Ax=b$. These conditions were also shown to be necessary for exponential convergence, provided the data about $[A;b]$ available to the agents is "non-redundant". The aim of this paper is to relax this "non-redundant" assumption. This is accomplished by establishing exponential convergence under conditions which are the weakest possible for the problem at hand; the conditions are based on a new notion of graph connectivity. An improved bound on the convergence rate is also derived.

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

Recommendations

• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Continuous distributed algorithms for solving linear equations in finite time
• scientific article; zbMATH DE number 7042406
• Distributed fixed point method for solving systems of linear algebraic equations
• Asynchronous Distributed Algorithms for Solving Linear Algebraic Equations
• Distributed algorithms with finite data rates that solve linear equations
• A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Distributed Algorithm for Solving Convex Inequalities
• A Randomized Solver for Linear Systems with Exponential Convergence

zbMATH Keywords

distributed algorithmexponential convergencesolving linear algebraic equations

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Decentralized systems (93A14) Linear systems in control theory (93C05)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Title not available (Why is that?)
• Consensus and Cooperation in Networked Multi-Agent Systems
• Constrained Consensus and Optimization in Multi-Agent Networks
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Stability of multiagent systems with time-dependent communication links
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Distributed Subgradient Methods for Multi-Agent Optimization
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Fast Distributed Gradient Methods
• Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs
• Decentralized gradient algorithm for solution of a linear equation
• Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
• Estimation From Relative Measurements: Electrical Analogy and Large Graphs
• On Distributed Averaging Algorithms and Quantization Effects
• Convexity and characterization of optimal policies in a dynamic routing problem
• Newton-Raphson Consensus for Distributed Convex Optimization
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Distributed Optimization Over Time-Varying Directed Graphs
• Error Scaling Laws for Linear Optimal Estimation From Relative Measurements
• Constrained Consensus in Unbalanced Networks With Communication Delays
• Asynchronous Distributed ADMM for Large-Scale Optimization—Part I: Algorithm and<?Pub _newline ?>Convergence Analysis
• Consensus‐based distributed sensor calibration and least‐square parameter identification in WSNs

Cited In (10)

• Distributed least squares solver for network linear equations
• Distributed algorithms of solving linear matrix equations via double-layered networks
• Distributed convex optimization based on ADMM and belief propagation methods
• Control-theoretic methods for solving linear algebraic equations: a continuous-time perspective
• Title not available (Why is that?)
• Designing linear distributed algorithms with memory for fast convergence
• Scalable distributed least square algorithms for large-scale linear equations via an optimization approach
• Continuous distributed algorithms for solving linear equations in finite time
• Distributed fixed point method for solving systems of linear algebraic equations
• Lyapunov based stochastic stability of a quantum decision system for human-machine interaction

This page was built for publication: Exponential convergence of a distributed algorithm for solving linear algebraic equations

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