Graph Effective Resistance and Distributed Control: Spectral Properties and Applications

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

I. Introduction

This paper considers undirected graphs with a weight associated with each one of its edges. The edge-weights are symmetric positive definite matrices. For such graphs we introduce the concept of “effective resistances.” The effective resistance of a node is defined to be a square matrix block that appears in the diagonal of the inverse of the matrix-weighted Dirichlet graph Laplacian matrix (cf. Section II). The terminology “effective resistance” is motivated by the fact that these matrices also define a linear map from currents to voltages in a generalized electrical network that can be constructed from the undirected matrix-weighted graph. However, the voltages, currents, and resistances in this generalized electrical network take matrix values [1].