  Many important geometric estimation problems take the form of synchronization
over the special Euclidean group: estimate the values of a set of poses given a
set of relative measurements between them. This problem is typically formulated
as a nonconvex maximum-likelihood estimation that is computationally hard to
solve in general. Nevertheless, in this paper we present an algorithm that is
able to efficiently recover certifiably globally optimal solutions of the
special Euclidean synchronization problem in a non-adversarial noise regime.
The crux of our approach is the development of a semidefinite relaxation of the
maximum-likelihood estimation whose minimizer provides an exact MLE so long as
the magnitude of the noise corrupting the available measurements falls below a
certain critical threshold; furthermore, whenever exactness obtains, it is
possible to verify this fact a posteriori, thereby certifying the optimality of
the recovered estimate. We develop a specialized optimization scheme for
solving large-scale instances of this relaxation by exploiting its low-rank,
geometric, and graph-theoretic structure to reduce it to an equivalent
optimization problem on a low-dimensional Riemannian manifold, and design a
truncated-Newton trust-region method to solve this reduction efficiently.
Finally, we combine this fast optimization approach with a simple rounding
procedure to produce our algorithm, SE-Sync. Experimental evaluation on a
variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync
is able to recover certifiably globally optimal solutions when the available
measurements are corrupted by noise up to an order of magnitude greater than
that typically encountered in robotics and computer vision applications, and
does so more than an order of magnitude faster than the Gauss-Newton-based
approach that forms the basis of current state-of-the-art techniques.
