A Cheeger Inequality for the Graph Connection Laplacian

Abstract

The $O(d)$ synchronization problem consists of estimating a set of $n$ unknown orthogonal $d\times d$ matrices $O_1,\ldots,O_n$ from noisy measurements of a subset of the pairwise ratios $O_iO_j^{-1}$. We formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the $O(d)$ synchronization problem with the spectra of an operator, the graph connection Laplacian. We also show how this inequality provides a worst-case performance guarantee for a spectral method to solve this problem.