Exact Recovery in Semidefinite Relaxation of Synchronization over E(1)

We consider the problem of synchronization over the Euclidean group in one dimension (E(1)): the goal is to recover n elements of such group (ground truth) from measurements of their pairwise products corrupted with non-adversarial noise. Informally this can be seen as the problem of determining the orientation and position of a ballerina that moves along a line and faces in one of two possible directions from poor quality photos.

While synchronization over E(1) is a nonconvex optimization problem, we showed that its semidefinite program (SDP) relaxation exactly recovers the orientation ground truth with high probability. This is demonstrated for any level of noise by leveraging non-asymptotic bounds for the spectral norm of random matrices with independent entries.

The recovery of the maximum likelihood estimator (MLE) of the position is tight, meaning that the solution derived from the SDP relaxation matches the MLE of the position ground truth with high probability. However, due to noise exact recovery of the position ground truth is not possible.

Synchronization over the special Euclidian group in d dimensions (SE(d)) includes important problems in robotics and computer vision. We expect that establishing the tightness of synchronization over SE(d) should be similar to establishing that over the Euclidian group in d dimensions (E(d)). Therefore, we hope that our result for E(1) will be extended to higher dimensions.

Papers