TY - JOUR

T1 - Consensus Based Distributed Spectral Radius Estimation

AU - Muniraju, Gowtham

AU - Tepedelenlioglu, Cihan

AU - Spanias, Andreas

N1 - Funding Information:
Manuscript received March 7, 2020; accepted June 8, 2020. Date of publication June 17, 2020; date of current version July 2, 2020. This work was supported in part by the NSF CPS award 1646542 and in part by the SenSIP Center, School of ECEE, Arizona State University. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Xun Cao. (Corresponding author: Gowtham Muniraju.) The authors are with the School of ECEE, Arizona State University, Tempe, AZ 82587 USA (e-mail: gmuniraj@asu.edu; cihan@asu.edu; spanias@asu.edu). Digital Object Identifier 10.1109/LSP.2020.3003237

PY - 2020

Y1 - 2020

N2 - A consensus based distributed algorithm to compute the spectral radius of a network is proposed. The spectral radius of the graph is the largest eigenvalue of the adjacency matrix, and is a useful characterization of the network graph. Conventionally, centralized methods are used to compute the spectral radius, which involves eigenvalue decomposition of the adjacency matrix of the underlying graph. Our distributed algorithm uses a simple update rule to reach consensus on the spectral radius, using only local communications. We consider time-varying graphs to model packet loss and imperfect transmissions, and provide the convergence characteristics of our algorithm, for both static and time-varying graphs. We prove that the convergence error is a function of principal eigenvector of adjacency matrix of the graph and reduces as $\mathcal {O}(1/t)$, where $t$ is the number of iterations. The algorithm works for any connected graph structure. Simulation results supporting the theory are also presented.

AB - A consensus based distributed algorithm to compute the spectral radius of a network is proposed. The spectral radius of the graph is the largest eigenvalue of the adjacency matrix, and is a useful characterization of the network graph. Conventionally, centralized methods are used to compute the spectral radius, which involves eigenvalue decomposition of the adjacency matrix of the underlying graph. Our distributed algorithm uses a simple update rule to reach consensus on the spectral radius, using only local communications. We consider time-varying graphs to model packet loss and imperfect transmissions, and provide the convergence characteristics of our algorithm, for both static and time-varying graphs. We prove that the convergence error is a function of principal eigenvector of adjacency matrix of the graph and reduces as $\mathcal {O}(1/t)$, where $t$ is the number of iterations. The algorithm works for any connected graph structure. Simulation results supporting the theory are also presented.

KW - Algebraic connectivity

KW - consensus

KW - distributed estimation

KW - spectral radius

UR - http://www.scopus.com/inward/record.url?scp=85089686702&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089686702&partnerID=8YFLogxK

U2 - 10.1109/LSP.2020.3003237

DO - 10.1109/LSP.2020.3003237

M3 - Article

AN - SCOPUS:85089686702

VL - 27

SP - 1045

EP - 1049

JO - IEEE Signal Processing Letters

JF - IEEE Signal Processing Letters

SN - 1070-9908

M1 - 9119754

ER -