Growing Linear Consensus Networks Endowed by Spectral Systemic Performance Measures
For control and network engineers, this provides a principled framework and efficient algorithms for designing large-scale consensus networks with provable performance guarantees.
The paper introduces a class of spectral systemic performance measures for noisy linear consensus networks and proposes two polynomial-time approximation algorithms for growing such networks by minimizing these measures. Theoretical performance limits are derived, and algorithms are shown to be effective for large-scale networks.
We propose an axiomatic approach for design and performance analysis of noisy linear consensus networks by introducing a notion of systemic performance measure. This class of measures are spectral functions of Laplacian eigenvalues of the network that are monotone, convex, and orthogonally invariant with respect to the Laplacian matrix of the network. It is shown that several existing gold-standard and widely used performance measures in the literature belong to this new class of measures. We build upon this new notion and investigate a general form of combinatorial problem of growing a linear consensus network via minimizing a given systemic performance measure. Two efficient polynomial-time approximation algorithms are devised to tackle this network synthesis problem: a linearization-based method and a simple greedy algorithm based on rank-one updates. Several theoretical fundamental limits on the best achievable performance for the combinatorial problem is derived that assist us to evaluate optimality gaps of our proposed algorithms. A detailed complexity analysis confirms the effectiveness and viability of our algorithms to handle large-scale consensus networks.