Revisiting Finite-Time Distributed Algorithms via Successive Nulling of Eigenvalues

In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a f...

Full description

Saved in:
Bibliographic Details
Published in:IEEE signal processing letters 2015-01, Vol.22 (1), p.54-57
Main Authors: Safavi, Sam, Khan, Usman A.
Format: Article
Language:English
Subjects:
Algebra
Average-consensus
Convergence
Distributed algorithms
Eigenvalue multiplicity
Eigenvalues
Eigenvalues and eigenfunctions
Eigenvectors
finite-time convergence
Graphs
Initial conditions
Linear operators
Mathematical analysis
Matrices
Multi-agent systems
Probability
Stress concentration
Subspaces
Topology
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a finite time. This subspace can be chosen to have the same dimension as the algebraic multiplicity of any (arbitrarily chosen) eigenvalue of the underlying linear operator and is spanned by the eigenvectors corresponding to the chosen eigenvalue. In other words, finite-time behavior is completely characterized by the algebraic multiplicity of the eigenvalues and the corresponding eigenvectors of the underlying linear operator. We show that finite-time average-consensus can be cast naturally in this setup for which we further develop the necessary and sufficient conditions.
ISSN:1070-9908
1558-2361
DOI:10.1109/LSP.2014.2346657