The O(d) synchronization problem consists of estimating a set of n unknown orthogonal d × d matrices O1, ... , On from noisy measurements of a subset of the pairwise ratios OiO-1j . 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.
All Science Journal Classification (ASJC) codes
- Cheeger inequality
- Graph connection Laplacian
- O(d) synchronization
- Vector diffusion maps