  The O(d) Synchronization problem consists of estimating a set of unknown
orthogonal transformations O_i 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.
