Distributed matrix scaling and application to average consensus in directed graphs

Alejandro D. Domínguez-García, Christoforos N. Hadjicostis

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a class of distributed iterative algorithms that enable the asymptotic scaling of a primitive column stochastic matrix, with a given sparsity structure, to a doubly stochastic form. We also demonstrate the application of these algorithms to the average consensus problem in networked multi-component systems. More specifically, we consider a setting where each node is in charge of assigning weights on its outgoing edges based on the weights on its incoming edges. We establish that, as long as the (generally directed) graph that describes the communication links between components is strongly connected, each of the proposed matrix scaling algorithms allows the system components to asymptotically assign, in a distributed fashion, weights that comprise a primitive doubly stochastic matrix. We also show that the nodes can asymptotically reach average consensus by executing a linear iteration that uses the time-varying weights (as they result at the end of each iteration of the chosen matrix scaling algorithm).

Original languageEnglish (US)
Article number6319365
Pages (from-to)667-681
Number of pages15
JournalIEEE Transactions on Automatic Control
Volume58
Issue number3
DOIs
StatePublished - 2013

Keywords

  • Average consensus
  • directed graph
  • distributed algorithms
  • matrix scaling
  • nonnegative matrix

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Distributed matrix scaling and application to average consensus in directed graphs'. Together they form a unique fingerprint.

Cite this