Distributed estimation of Laplacian eigenvalues via constrained consensus optimization problems

From the recent literature, we know that some consecutive measurements of the consensus protocol can be used to compute the exact average of the initial condition. In this paper, we show that these measurements can also be used for estimating the Laplacian eigenvalues of the graph representing the network. As recently shown in the literature, by solving the factorization of the averaging matrix, the Laplacian eigenvalues can be inferred. Herein, the problem is posed as a constrained consensus problem formulated two-fold. The first formulation (direct approach) yields a non-convex optimization problem solved in a distributed way by means of the method of Lagrange multipliers. The second formulation (indirect approach) is obtained after an adequate re-parameterization. The problem is then convex and is solved by using the distributed subgradient algorithm and the alternating direction method of multipliers (ADMM). The proposed algorithms allow estimating the actual Laplacian eigenvalues with high accuracy.