SE-Sync

SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group. 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.


References in zbMATH (referenced in 12 articles )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Bai, Fang; Bartoli, Adrien: Procrustes analysis with deformations: a closed-form solution by eigenvalue decomposition (2022)
  2. Brynte, Lucas; Larsson, Viktor; Iglesias, José Pedro; Olsson, Carl; Kahl, Fredrik: On the tightness of semidefinite relaxations for rotation estimation (2022)
  3. Ling, Shuyang: Improved performance guarantees for orthogonal group synchronization via generalized power method (2022)
  4. Cifuentes, Diego: A convex relaxation to compute the nearest structured rank deficient matrix (2021)
  5. Garcia-Salguero, Mercedes; Gonzalez-Jimenez, Javier: Fast and robust certifiable estimation of the relative pose between two calibrated cameras (2021)
  6. Rosen, David M.: Scalable low-rank semidefinite programming for certifiably correct machine perception (2021)
  7. Yurtsever, Alp; Tropp, Joel A.; Fercoq, Olivier; Udell, Madeleine; Cevher, Volkan: Scalable semidefinite programming (2021)
  8. Arrigoni, Federica; Fusiello, Andrea: Synchronization problems in computer vision with closed-form solutions (2020)
  9. Romanov, Elad; Gavish, Matan: The noise-sensitivity phase transition in spectral group synchronization over compact groups (2020)
  10. Waldspurger, Irène; Waters, Alden: Rank optimality for the Burer-Monteiro factorization (2020)
  11. Zhao, Liang; Huang, Shoudong; Dissanayake, Gamini: Linear SLAM: linearising the SLAM problems using submap joining (2019)
  12. Wang, Heng; Huang, Shoudong; Yang, Guanghong; Dissanayake, Gamini: Comparison of two different objective functions in 2D point feature SLAM (2018)