# Distributed Estimation of Graph Spectrum

arXiv: https://arxiv.org/abs/1503.08192 · HTML: https://mlsanity.com/paper/1503.08192/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)

## Abstract (arXiv)

In this paper, we develop a two-stage distributed algorithm that enables nodes in a graph to cooperatively estimate the spectrum of a matrix W associated with the graph, which includes the adjacency and Laplacian matrices as special cases. In the first stage, the algorithm uses a discrete-time linear iteration and the Cayley-Hamilton theorem to convert the problem into one of solving a set of linear equations, where each equation is known to a node. In the second stage, if the nodes happen to know that W is cyclic, the algorithm uses a Lyapunov approach to asymptotically solve the equations with an exponential rate of convergence. If they do not know whether W is cyclic, the algorithm uses a random perturbation approach and a structural controllability result to approximately solve the equations with an error that can be made small. Finally, we provide simulation results that illustrate the algorithm.