Consensus-based distributed estimation of Laplacian eigenvalues of undirected graphs

In this paper, we present a novel algorithm for estimating eigenvalues of the Laplacian matrix associated with the graph describing the network topology of a multi-agent system or a wireless sensor network. As recently shown, the average consensus matrix can be written as a product of Laplacian based consensus matrices whose stepsizes are given by the inverse of the nonzero Laplacian eigenvalues. Therefore, by solving the factorization of the average consensus matrix, we can infer the Laplacian eigenvalues. We show how solving such a matrix factorization problem in a distributed way. In particular, we formulate the problem as a constrained consensus problem. The proposed algorithm does not require great resources in both computation and storage. This algorithm can also be viewed as a way for decentralizing the design of finite-time average consensus protocol recently proposed in the literature. Eventually, the performance of the proposed algorithm is evaluated by means of simulation results.