Network Sparsification with Guaranteed Systemic Performance Measures

A sparse consensus network is one whose number of coupling links is proportional to its number of subsystems. Optimal design problems for sparse consensus networks are more amenable to efficient optimization algorithms. More importantly, maintaining such networks are usually more cost effective due to their reduced communication requirements. Therefore, approximating a given dense consensus network by a suitable sparse network is an important analysis and synthesis problem. In this paper, we develop a framework to produce a sparse approximation of a given large-scale network with guaranteed performance bounds using a nearly-linear time algorithm. First, the existence of a sparse approximation of a given network is proven. Then, we present an efficient and fast algorithm for finding a near-optimal sparse approximation of a given network. Finally, several examples are provided to support our theoretical developments.