Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 1611-1630 |
Number of pages | 20 |
Journal | SIAM Journal on Matrix Analysis and Applications |
Volume | 34 |
Issue number | 4 |
DOIs | |
State | Published - 2013 |
All Science Journal Classification (ASJC) codes
- Analysis
Keywords
- Cheeger inequality
- Graph connection Laplacian
- O(d) synchronization
- Vector diffusion maps