A Certifiably Correct Algorithm for Synchronization over the Special\n Euclidean Group

Abstract

Many geometric estimation problems take the form of synchronization over the\nspecial Euclidean group: estimate the values of a set of poses given noisy\nmeasurements of a subset of their pairwise relative transforms. This problem is\ntypically formulated as a maximum-likelihood estimation that requires solving a\nnonconvex nonlinear program, which is computationally intractable in general.\nNevertheless, in this paper we present an algorithm that is able to efficiently\nrecover certifiably globally optimal solutions of this estimation problem in a\nnon-adversarial noise regime. The crux of our approach is the development of a\nsemidefinite relaxation of the maximum-likelihood estimation whose minimizer\nprovides the exact MLE so long as the magnitude of the noise corrupting the\navailable measurements falls below a certain critical threshold; furthermore,\nwhenever exactness obtains, it is possible to verify this fact a posteriori,\nthereby certifying the optimality of the recovered estimate. We develop a\nspecialized optimization scheme for solving large-scale instances of this\nsemidefinite relaxation by exploiting its low-rank, geometric, and\ngraph-theoretic structure to reduce it to an equivalent optimization problem on\na low-dimensional Riemannian manifold, and then design a Riemannian\ntruncated-Newton trust-region method to solve this reduction efficiently. We\ncombine this fast optimization approach with a simple rounding procedure to\nproduce our algorithm, SE-Sync. Experimental evaluation on a variety of\nsimulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable\nof recovering globally optimal solutions when the available measurements are\ncorrupted by noise up to an order of magnitude greater than that typically\nencountered in robotics applications, and does so at a computational cost that\nscales comparably with that of direct Newton-type local search techniques.\n