Paper Info
Title
Distributed Computation Of The Perron-Frobenius Eigenvector
Abstract
The Perron-Frobenius theorem has numerous applications, including to Markov chains, economics, and ranking of webpages. In this paper, we develop a class of continuous-time distributed algorithms and a gossip algorithm, which enable each node i in an undirected and connected graph to compute the ith entry of the Perron-Frobenius eigenvector of a symmetric, Metzler, and irreducible matrix associated with the graph, as well as the corresponding eigenvalue, when node i knows only row i of the matrix. We show that each continuous-time distributed algorithm in the class is a nonlinear networked dynamical system with a skew-symmetric structure, whose state is guaranteed to stay on a sphere, remain nonnegative, and converge asymptotically to the said eigenvector. We also show that under a mild assumption on the gossiping pattern, the gossip algorithm is able to do the same.
Year
Venue
Field
2016
2016 IEEE 55TH CONFERENCE ON DECISION AND CONTROL (CDC)
Discrete mathematics,Mathematical optimization,Combinatorics,Algorithm design,Stochastic matrix,Matrix (mathematics),Computer science,Markov chain,Symmetric matrix,Distributed algorithm,Connectivity,Eigenvalues and eigenvectors
DocType
ISSN
Citations 
Conference
0743-1546
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Mu Yang100.34
Choon Yik Tang28512.90