SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group
Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements (Formula presented.) given noisy measurements of a subset of their pairwise relative transforms (Formula presented.). Examp...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Sage Publications
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120180 https://orcid.org/0000-0001-8964-1602 https://orcid.org/0000-0003-1884-5397 https://orcid.org/0000-0002-8863-6550 |
| _version_ | 1811080506974928896 |
|---|---|
| author | Bandeira, Afonso S Rosen, David Matthew Carlone, Luca Leonard, John J |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bandeira, Afonso S Rosen, David Matthew Carlone, Luca Leonard, John J |
| author_sort | Bandeira, Afonso S |
| collection | MIT |
| description | Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements (Formula presented.) given noisy measurements of a subset of their pairwise relative transforms (Formula presented.). Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex 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 (MLE) whose minimizer provides an exact maximum-likelihood estimate 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 semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian 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 capable of recovering 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 significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques. |
| first_indexed | 2024-09-23T11:32:45Z |
| format | Article |
| id | mit-1721.1/120180 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:32:45Z |
| publishDate | 2019 |
| publisher | Sage Publications |
| record_format | dspace |
| spelling | mit-1721.1/1201802022-10-01T04:22:31Z SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group Bandeira, Afonso S Rosen, David Matthew Carlone, Luca Leonard, John J Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Mechanical Engineering Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Rosen, David Matthew Carlone, Luca Leonard, John J Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements (Formula presented.) given noisy measurements of a subset of their pairwise relative transforms (Formula presented.). Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex 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 (MLE) whose minimizer provides an exact maximum-likelihood estimate 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 semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian 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 capable of recovering 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 significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques. 2019-02-04T19:28:37Z 2019-02-04T19:28:37Z 2018-08 2018-12-12T15:14:37Z Article http://purl.org/eprint/type/JournalArticle 0278-3649 1741-3176 http://hdl.handle.net/1721.1/120180 Rosen, David M, Luca Carlone, Afonso S Bandeira, and John J Leonard. “SE-Sync: a Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group.” The International Journal of Robotics Research (August 29, 2018): 027836491878436. © 2018 The Authors https://orcid.org/0000-0001-8964-1602 https://orcid.org/0000-0003-1884-5397 https://orcid.org/0000-0002-8863-6550 http://dx.doi.org/10.1177/0278364918784361 The International Journal of Robotics Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Sage Publications arXiv |
| spellingShingle | Bandeira, Afonso S Rosen, David Matthew Carlone, Luca Leonard, John J SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title | SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title_full | SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title_fullStr | SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title_full_unstemmed | SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title_short | SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group |
| title_sort | se sync a certifiably correct algorithm for synchronization over the special euclidean group |
| url | http://hdl.handle.net/1721.1/120180 https://orcid.org/0000-0001-8964-1602 https://orcid.org/0000-0003-1884-5397 https://orcid.org/0000-0002-8863-6550 |
| work_keys_str_mv | AT bandeiraafonsos sesyncacertifiablycorrectalgorithmforsynchronizationoverthespecialeuclideangroup AT rosendavidmatthew sesyncacertifiablycorrectalgorithmforsynchronizationoverthespecialeuclideangroup AT carloneluca sesyncacertifiablycorrectalgorithmforsynchronizationoverthespecialeuclideangroup AT leonardjohnj sesyncacertifiablycorrectalgorithmforsynchronizationoverthespecialeuclideangroup |