Graph Effective Resistance and Distributed Control: Spectral Properties and Applications

Abstract

We introduce the concept of matrix-valued effective resistance for undirected matrix-weighted graphs. Effective resistances are defined to be the square blocks that appear in the diagonal of the inverse of the matrix-weighted Dirichlet graph Laplacian matrix. However, they can also be obtained from a "generalized" electrical network that is constructed from the graph, and for which currents, voltages and resistances take matrix values. Effective resistances play an important role in several problems related to distributed control and estimation. They appear in least-squares estimation problems in which one attempts to reconstruct global information from relative noisy measurements; as well as in motion control problems in which agents attempt to control their positions towards a desired formation, based on noisy local measurements. We show that in either of these problems, the effective resistances have a direct physical interpretation. We also show that effective resistances provide bounds on the spectrum of the graph Laplacian matrix and the Dirichlet graph Laplacian. These bounds can be used to characterize the stability and convergence rate of several distributed algorithms that appeared in the literature