{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T18:03:31Z","timestamp":1774029811090,"version":"3.50.1"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030430887","type":"print"},{"value":"9783030430894","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-43089-4_5","type":"book-chapter","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:04:08Z","timestamp":1588781048000},"page":"64-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group"],"prefix":"10.1007","author":[{"given":"David M.","family":"Rosen","sequence":"first","affiliation":[]},{"given":"Luca","family":"Carlone","sequence":"additional","affiliation":[]},{"given":"Afonso S.","family":"Bandeira","sequence":"additional","affiliation":[]},{"given":"John J.","family":"Leonard","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,7]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"P.-A. Absil, C.G. Baker, and K.A. Gallivan. Trust-region methods on Riemannian manifolds. Found. Comput. Math., 7(3):303\u2013330, July 2007.","DOI":"10.1007\/s10208-005-0179-9"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.","DOI":"10.1515\/9781400830244"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"R. Aragues, L. Carlone, G. Calafiore, and C. Sagues. Multi-agent localization from noisy relative pose measurements. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 364\u2013369, Shanghai, China, May 2011.","DOI":"10.1109\/ICRA.2011.5979799"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"A.S. Bandeira. A note on probably certifiably correct algorithms. Comptes Rendus Mathematique, 354(3):329\u2013333, 2016.","DOI":"10.1016\/j.crma.2015.11.009"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"A.S. Bandeira, N. Boumal, and A. Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program., 2016.","DOI":"10.1007\/s10107-016-1059-6"},{"key":"5_CR6","unstructured":"N. Boumal. A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints. arXiv preprint: \narXiv:1506.00575v2\n\n, 2015."},{"key":"5_CR7","unstructured":"N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, a MATLAB toolbox for optimization on manifolds. Journal of Machine Learning Research, 15(1):1455\u20131459, 2014."},{"key":"5_CR8","unstructured":"N. Boumal, P.-A. Absil, and C. Cartis. Global rates of convergence for nonconvex optimization on manifolds. arXiv preprint: \narXiv:1605.08101v1\n\n, 2016."},{"key":"5_CR9","unstructured":"N. Boumal, V. Voroninski, and A.S. Bandeira. The non-convex Burer- Monteiro approach works on smooth semidefinite programs. arXiv preprint \narXiv:1606.04970v1\n\n, June 2016."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"S. Burer and R.D.C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program.,95:329\u2013357, 2003.","DOI":"10.1007\/s10107-002-0352-8"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"S. Burer and R.D.C. Monteiro. Local minima and convergence in low-rank semidefinite programming. Math. Program., 103:427\u2013444, 2005.","DOI":"10.1007\/s10107-004-0564-1"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"L. Carlone and A. Censi. From angular manifolds to the integer lattice: Guaranteed orientation estimation with application to pose graph optimization. IEEE Trans. on Robotics, 30(2):475\u2013492, April 2014.","DOI":"10.1109\/TRO.2013.2291626"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"L. Carlone and F. Dellaert. Duality-based verification techniques for 2D SLAM. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 4589\u20134596, Seattle, WA, May 2015.","DOI":"10.1109\/ICRA.2015.7139835"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"L. Carlone, D.M. Rosen, G. Calafiore, J.J. Leonard, and F. Dellaert. Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions. In IEEE\/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), Hamburg, Germany, September 2015.","DOI":"10.1109\/IROS.2015.7353364"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"L. Carlone, R. Tron, K. Daniilidis, and F. Dellaert. Initialization techniques for 3D SLAM: A survey on rotation estimation and its use in pose graph optimization. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 4597\u20134605, Seattle, WA, May 2015.","DOI":"10.1109\/ICRA.2015.7139836"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"L. Carlone, G.C. Calafiore, C. Tommolillo, and F. Dellaert. Planar pose graph optimization: Duality, optimal solutions, and verification. IEEE Trans. on Robotics, 32(3):545\u2013565, June 2016.","DOI":"10.1109\/TRO.2016.2544304"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"A. Chiuso, G. Picci, and S. Soatto. Wide-sense estimation on the special orthogonal group. Communications in Information and Systems, 8(3):185\u2013200, 2008.","DOI":"10.4310\/CIS.2008.v8.n3.a1"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"F. Dellaert and M. Kaess. Square Root SAM: Simultaneous localization and mapping via square root information smoothing. Intl. J. of Robotics Research, 25(12):1181\u20131203, December 2006.","DOI":"10.1177\/0278364906072768"},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"A. Edelman, T.A. Arias, and S.T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl., 20(2):303\u2013353, October 1998.","DOI":"10.1137\/S0895479895290954"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"T.S. Ferguson. A Course in Large Sample Theory. Chapman & Hall\/CRC, Boca Raton, FL, 1996.","DOI":"10.1007\/978-1-4899-4549-5"},{"key":"5_CR21","unstructured":"J. Gallier. The Schur complement and symmetric positive semidefinite (and definite) matrices. unpublished note, available online: \nhttp:\/\/www.cis.upenn.edu\/~jean\/schur-comp.pdf\n\n, December 2010."},{"key":"5_CR22","unstructured":"G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 3rd edition, 1996."},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"G. Grisetti, C. Stachniss, and W. Burgard. Nonlinear constraint network optimization for efficient map learning. IEEE Trans. on Intelligent Transportation Systems, 10(3):428\u2013439, September 2009.","DOI":"10.1109\/TITS.2009.2026444"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"G. Grisetti, R. K\u00fcmmerle, C. Stachniss, and W. Burgard. A tutorial on graph-based SLAM. IEEE Intelligent Transportation Systems Magazine, 2 (4):31\u201343, 2010.","DOI":"10.1109\/MITS.2010.939925"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"R. Hartley, J. Trumpf, Y. Dai, and H. Li. Rotation averaging. Intl. J. of Computer Vision, 103(3):267\u2013305, July 2013.","DOI":"10.1007\/s11263-012-0601-0"},{"key":"5_CR26","unstructured":"S. Huang, Y. Lai, U. Frese, and G. Dissanayake. How far is SLAM from a linear least squares problem? In IEEE\/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), pages 3011\u20133016, Taipei, Taiwan, October 2010."},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"S. Huang, H. Wang, U. Frese, and G. Dissanayake. On the number of local minima to the point feature based SLAM problem. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 2074\u20132079, St. Paul, MN, May 2012.","DOI":"10.1109\/ICRA.2012.6224876"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"M. Kaess, H. Johannsson, R. Roberts, V. Ila, J.J. Leonard, and F. Dellaert. iSAM2: Incremental smoothing and mapping using the Bayes tree. Intl. J. of Robotics Research, 31(2):216\u2013235, February 2012.","DOI":"10.1177\/0278364911430419"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"R. K\u00fcmmerle, G. Grisetti, H. Strasdat, K. Konolige, and W. Burgard. g2o: A general framework for graph optimization. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 3607\u20133613, Shanghai, China, May 2011.","DOI":"10.1109\/ICRA.2011.5979949"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"F. Lu and E. Milios. Globally consistent range scan alignment for environmental mapping. Autonomous Robots, 4:333\u2013349, April 1997.","DOI":"10.1023\/A:1008854305733"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Z.-Q. Luo, W.-K. Ma, A. So, Y. Ye, and S. Zhang. Semidefinite relaxation of quadratic optimization problems. IEEE Signal Processing Magazine, 27 (3):20\u201334, May 2010.","DOI":"10.1109\/MSP.2010.936019"},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"D. Martinec and T. Pajdla. Robust rotation and translation estimation in multiview reconstruction. In IEEE Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), pages 1\u20138, Minneapolis, MN, June 2007.","DOI":"10.1109\/CVPR.2007.383115"},{"key":"5_CR33","unstructured":"J. Nocedal and S.J. Wright. Numerical Optimization. Springer Science+Business Media, New York, 2nd edition, 2006."},{"key":"5_CR34","unstructured":"E. Olson, J.J. Leonard, and S. Teller. Fast iterative alignment of pose graphs with poor initial estimates. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 2262\u20132269, Orlando, FL, May 2006."},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"J.R. Peters, D. Borra, B.E. Paden, and F. Bullo. Sensor network localization on the group of three-dimensional displacements. SIAM J. Control Optim., 53(6):3534\u20133561, 2015.","DOI":"10.1137\/140957743"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"D.M. Rosen, M. Kaess, and J.J. Leonard. RISE: An incremental trust-region method for robust online sparse least-squares estimation. IEEE Trans. on Robotics, 30(5):1091\u20131108, October 2014.","DOI":"10.1109\/TRO.2014.2321852"},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"D.M. Rosen, C. DuHadway, and J.J. Leonard. A convex relaxation for approximate global optimization in simultaneous localization and mapping. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 5822\u20135829, Seattle, WA, May 2015.","DOI":"10.1109\/ICRA.2015.7140014"},{"key":"5_CR38","unstructured":"D.M. Rosen, L. Carlone, A.S. Bandeira, and J.J. Leonard. SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group. Technical Report MIT-CSAIL-TR-2017-002, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, February 2017."},{"key":"5_CR39","doi-asserted-by":"crossref","unstructured":"A. Singer and Y. Shkolnisky. Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming. SIAM J. Imaging Sci., 4(2):543\u2013572, 2011.","DOI":"10.1137\/090767777"},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"A. Singer and H.-T. Wu. Vector di?usion maps and the connection Laplacian. Comm. Pure Appl. Math., 65:1067\u20131144, 2012.","DOI":"10.1002\/cpa.21395"},{"key":"5_CR41","doi-asserted-by":"crossref","unstructured":"M.J. Todd. Semidefinite optimization. Acta Numerica, 10:515\u2013560, 2001.","DOI":"10.1017\/S0962492901000071"},{"key":"5_CR42","doi-asserted-by":"crossref","unstructured":"R. Tron and R. Vidal. Distributed 3-D localization of camera sensor networks from 2-D image measurements. IEEE Trans. on Automatic Control, 59(12):3325\u20133340, December 2014.","DOI":"10.1109\/TAC.2014.2351912"},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"S. Umeyama. Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. on Pattern Analysis and Machine Intelligence, 13(4):376\u2013380, 1991.","DOI":"10.1109\/34.88573"},{"key":"5_CR44","doi-asserted-by":"crossref","unstructured":"V. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49\u201395, March 1996.","DOI":"10.1137\/1038003"},{"key":"5_CR45","doi-asserted-by":"crossref","unstructured":"H. Wang, G. Hu, S. Huang, and G. Dissanayake. On the structure of nonlinearities in pose graph SLAM. In Robotics: Science and Systems (RSS), Sydney, Australia, July 2012.","DOI":"10.15607\/RSS.2012.VIII.054"},{"key":"5_CR46","doi-asserted-by":"crossref","unstructured":"L. Wang and A. Singer. Exact and stable recovery of rotations for robust synchronization. Information and Inference, September 2013.","DOI":"10.1093\/imaiai\/iat005"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-43089-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:08:21Z","timestamp":1588781301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-43089-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030430887","9783030430894"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-43089-4_5","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"value":"2511-1256","type":"print"},{"value":"2511-1264","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"7 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}