{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T09:16:05Z","timestamp":1780391765214,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T00:00:00Z","timestamp":1633564800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T00:00:00Z","timestamp":1633564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001729","name":"Stiftelsen f\u00f6r Strategisk Forskning","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["2018-05375"],"award-info":[{"award-number":["2018-05375"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Math Imaging Vis"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Why is it that semidefinite relaxations have been so successful in numerous applications in computer vision and robotics for solving non-convex optimization problems involving rotations? In studying the empirical performance, we note that there are few failure cases reported in the literature, in particular for estimation problems with a single rotation, motivating us to gain further theoretical understanding. A general framework based on tools from algebraic geometry is introduced for analyzing the power of semidefinite relaxations of problems with quadratic objective functions and rotational constraints. Applications include registration, hand\u2013eye calibration, and rotation averaging. We characterize the extreme points and show that there exist failure cases for which the relaxation is not tight, even in the case of a single rotation. We also show that some problem classes are always tight given an appropriate parametrization. Our theoretical findings are accompanied with numerical simulations, providing further evidence and understanding of the results.<\/jats:p>","DOI":"10.1007\/s10851-021-01054-y","type":"journal-article","created":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T18:46:29Z","timestamp":1633632389000},"page":"57-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["On the Tightness of Semidefinite Relaxations for Rotation Estimation"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0794-291X","authenticated-orcid":false,"given":"Lucas","family":"Brynte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viktor","family":"Larsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jos\u00e9 Pedro","family":"Iglesias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carl","family":"Olsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fredrik","family":"Kahl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,10,7]]},"reference":[{"key":"1054_CR1","doi-asserted-by":"crossref","unstructured":"Arrigoni, F., Magri, L., Rossi, B., Fragneto, P., Fusiello, A.: Robust absolute rotation estimation via low-rank and sparse matrix decomposition. In: International Conference on 3D Vision (2014)","DOI":"10.1109\/3DV.2014.48"},{"issue":"2","key":"1054_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/34.121791","volume":"14","author":"P Besl","year":"1992","unstructured":"Besl, P., McKay, N.: A method for registration two 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239\u2013256 (1992)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1054_CR3","first-page":"673","volume":"10","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite optimization and convex algebraic geometry. SIAM J. Opt. 10, 673\u2013696 (2012)","journal-title":"SIAM J. Opt."},{"issue":"3","key":"1054_CR4","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1090\/jams\/847","volume":"29","author":"G Blekherman","year":"2016","unstructured":"Blekherman, G., Smith, G., Velasco, M.: Sums of squares and varieties of minimal degree. J. Am. Math. Soc. 29(3), 893\u2013913 (2016)","journal-title":"J. Am. Math. Soc."},{"key":"1054_CR5","unstructured":"Boumal, N.: A riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints. arXiv preprint arXiv:1506.00575 (2015)"},{"key":"1054_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"1054_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-7486-3_11","volume-title":"The Degree of $$SO(n, \\mathbb{C})$$","author":"M Brandt","year":"2017","unstructured":"Brandt, M., Bruce, J., Brysiewicz, T., Krone, R., Robeva, E.: The Degree of $$SO(n, \\mathbb{C})$$. Springer, New York (2017). https:\/\/doi.org\/10.1007\/978-1-4939-7486-3_11"},{"key":"1054_CR8","doi-asserted-by":"crossref","unstructured":"Briales, J., Gonzalez-Jimenez, J.: Fast global optimality verification in 3D SLAM. In: International Conference on Intelligent Robots and Systems (2016)","DOI":"10.1109\/IROS.2016.7759681"},{"key":"1054_CR9","doi-asserted-by":"crossref","unstructured":"Briales, J., Gonzalez-Jimenez, J.: Convex global 3D registration with Lagrangian duality. In: Computer Vision and Pattern Recognition (2017)","DOI":"10.1109\/CVPR.2017.595"},{"key":"1054_CR10","unstructured":"Brynte, L., Kahl, F.: bmvc. Pose Proposal Critic: Robust Pose Refinement by Learning Reprojection Errors. In: British Machine Vision Conference (2020)"},{"issue":"3","key":"1054_CR11","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1109\/TRO.2016.2544304","volume":"32","author":"L Carlone","year":"2016","unstructured":"Carlone, L., Calafiore, G.C., Tommolillo, C., Dellaert, F.: Planar pose graph optimization: duality, optimal solutions, and verification. IEEE Trans. Robot. 32(3), 545\u2013565 (2016). https:\/\/doi.org\/10.1109\/TRO.2016.2544304","journal-title":"IEEE Trans. Robot."},{"key":"1054_CR12","doi-asserted-by":"crossref","unstructured":"Carlone, L., Rosen, D.M., Calafiore, G., Leonard, J.J., Dellaert, F.: Lagrangian duality in 3D SLAM: verification techniques and optimal solutions. In: International Conference on Intelligent Robots and Systems (2015)","DOI":"10.1109\/IROS.2015.7353364"},{"key":"1054_CR13","doi-asserted-by":"crossref","unstructured":"Chatterjee, A., Govindu, V.: Efficient and robust large-scale rotation averaging. In: International Conference on Computer Vision (2013)","DOI":"10.1109\/ICCV.2013.70"},{"issue":"1","key":"1054_CR14","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1137\/130935458","volume":"25","author":"K Chaudhury","year":"2015","unstructured":"Chaudhury, K., Khoo, Y., Singer, A.: Global registration of multiple point clouds using semidefinite programming. SIAM J. Opt. 25(1), 468\u2013501 (2015)","journal-title":"SIAM J. Opt."},{"key":"1054_CR15","unstructured":"Cifuentes, D., Agarwal, S., Parrilo, P.A., Thomas, R.R.: On the local stability of semidefinite relaxations. arXiv preprint arXiv:1710.04287 (2017)"},{"issue":"1\/2","key":"1054_CR16","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10107-019-01399-8","volume":"182","author":"D Cifuentes","year":"2020","unstructured":"Cifuentes, D., Harris, C., Sturmfels, B.: The geometry of SDP-exactness in quadratic optimization. Math. Program. 182(1\/2), 399\u2013428 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01399-8","journal-title":"Math. Program."},{"key":"1054_CR17","doi-asserted-by":"crossref","unstructured":"Dellaert, F., Rosen, D., Wu, J., Mahony, R., Carlone, L.: Shonan rotation averaging: global optimality by surfing $$SO(p)^n$$. In: European Conference on computer vision (ECCV) (2020)","DOI":"10.1007\/978-3-030-58539-6_18"},{"key":"1054_CR18","first-page":"256","volume":"43","author":"A Eriksson","year":"2019","unstructured":"Eriksson, A., Olsson, C., Kahl, F., Chin, T.J.: Rotation averaging with the chordal distance: global minimizers and strong duality. IEEE Trans. Pattern Anal. Mach. Intell. 43, 256\u2013268 (2019)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6","key":"1054_CR19","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1109\/TRO.2020.3006717","volume":"36","author":"T Fan","year":"2020","unstructured":"Fan, T., Wang, H., Rubenstein, M., Murphey, T.: Cpl-slam: efficient and certifiably correct planar graph-based slam using the complex number representation. IEEE Trans. Robot. 36(6), 1719\u20131737 (2020). https:\/\/doi.org\/10.1109\/TRO.2020.3006717","journal-title":"IEEE Trans. Robot."},{"key":"1054_CR20","doi-asserted-by":"crossref","unstructured":"Fredriksson, J., Olsson, C.: Simultaneous multiple rotation averaging using Lagrangian duality. In: Asian Conference on Computer Vision (ACCV) (2012)","DOI":"10.1007\/978-3-642-37431-9_19"},{"issue":"2","key":"1054_CR21","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1109\/LRA.2018.2890444","volume":"4","author":"M Giamou","year":"2019","unstructured":"Giamou, M., Ma, Z., Peretroukhin, V., Kelly, J.: Certifiably globally optimal extrinsic calibration from per-sensor egomotion. IEEE Robot. Autom. Lett. 4(2), 367\u2013374 (2019)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"1054_CR22","unstructured":"Govindu, V.: Combining two-view constraints for motion estimation. In: Computer Vision and Pattern Recognition (2001)"},{"key":"1054_CR23","doi-asserted-by":"crossref","unstructured":"Hartley, R., Aftab, K., Trumpf, J.: $$L_1$$ rotation averaging using the Weiszfeld algorithm. In: IEEE Conference on Computer Vision and Pattern Recognition (2011)","DOI":"10.1109\/CVPR.2011.5995745"},{"issue":"3","key":"1054_CR24","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s11263-012-0601-0","volume":"103","author":"R Hartley","year":"2013","unstructured":"Hartley, R., Trumpf, J., Dai, Y., Li, H.: Rotation averaging. Int. J. Comput. Vis. IJCV 103(3), 267\u2013305 (2013)","journal-title":"Int. J. Comput. Vis. IJCV"},{"key":"1054_CR25","doi-asserted-by":"publisher","DOI":"10.1142\/q0252","volume-title":"The Moment-SOS Hierarchy","author":"D Henrion","year":"2020","unstructured":"Henrion, D., Korda, M., Lasserre, J.B.: The Moment-SOS Hierarchy. World Scientific, Singapore (2020). https:\/\/doi.org\/10.1142\/q0252"},{"issue":"3","key":"1054_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1177\/027836499501400301","volume":"14","author":"R Horaud","year":"1995","unstructured":"Horaud, R., Dornaika, F.: Hand-eye calibration. Int. J. Robot. Res. 14(3), 195\u2013210 (1995)","journal-title":"Int. J. Robot. Res."},{"issue":"4","key":"1054_CR27","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1364\/JOSAA.4.000629","volume":"4","author":"BKP Horn","year":"1987","unstructured":"Horn, B.K.P.: Closed-form solution of absolute orientation using unit quaternions. J. Opt. Soc. Am. A 4(4), 629\u2013642 (1987)","journal-title":"J. Opt. Soc. Am. A"},{"key":"1054_CR28","doi-asserted-by":"crossref","unstructured":"Iglesias, J., Olsson, C., Kahl, F.: Global optimality for point set registration using semidefinite programming. In: Computer Vision and Pattern Recognition (2020)","DOI":"10.1109\/CVPR42600.2020.00831"},{"issue":"1","key":"1054_CR29","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11263-006-0015-y","volume":"74","author":"F Kahl","year":"2007","unstructured":"Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. Int. J. Comput. Vis. IJCV 74(1), 3\u201315 (2007). https:\/\/doi.org\/10.1007\/s11263-006-0015-y","journal-title":"Int. J. Comput. Vis. IJCV"},{"issue":"3","key":"1054_CR30","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Opt. 11(3), 796\u2013817 (2001). https:\/\/doi.org\/10.1137\/S1052623400366802","journal-title":"SIAM J. Opt."},{"key":"1054_CR31","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/s13675-015-0050-y","volume":"5","author":"JB Lasserre","year":"2015","unstructured":"Lasserre, J.B., Toh, K.C., Yang, S.: A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Opt. 5, 10 (2015). https:\/\/doi.org\/10.1007\/s13675-015-0050-y","journal-title":"EURO J. Comput. Opt."},{"key":"1054_CR32","doi-asserted-by":"crossref","unstructured":"Mangelson, J., Liu, J., Eustice, R., Vasudevan, R.: Guaranteed globally optimal planar pose graph and landmark slam via sparse-bounded sums-of-squares programming. In: International Conference on Robotics and Automation (2019)","DOI":"10.1109\/ICRA.2019.8794454"},{"key":"1054_CR33","doi-asserted-by":"crossref","unstructured":"Nakano, G.: Globally optimal DLS method for PnP problem with Cayley parameterization. In: British Machine Vision Conference (2015)","DOI":"10.5244\/C.29.78"},{"key":"1054_CR34","unstructured":"Olsson, C., Kahl, F., Oskarsson, M.: The registration problem revisited: optimal solutions from points, lines and planes. In: Computer Vision and Pattern Recognition (2006)"},{"issue":"5","key":"1054_CR35","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1109\/TPAMI.2008.131","volume":"31","author":"C Olsson","year":"2009","unstructured":"Olsson, C., Kahl, F., Oskarsson, M.: Branch-and-bound methods for Euclidean registration problems. IEEE Trans. Pattern Anal. Mach. Intell. 31(5), 783\u2013794 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2\u20133","key":"1054_CR36","first-page":"95","volume":"38","author":"D Rosen","year":"2018","unstructured":"Rosen, D., Carlone, L., Bandeira, A., Leonard, J.: SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group. Int. J. Robot. Res. 38(2\u20133), 95\u2013125 (2018)","journal-title":"Int. J. Robot. Res."},{"issue":"2","key":"1054_CR37","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1112\/S002557931100132X","volume":"57","author":"R Sanyal","year":"2011","unstructured":"Sanyal, R., Sottile, F., Sturmfels, B.: Orbitopes. Mathematika 57(2), 275\u2013314 (2011)","journal-title":"Mathematika"},{"key":"1054_CR38","doi-asserted-by":"crossref","unstructured":"Sweeney, C., Fragoso, V., H\u00f6llerer, T., Turk, M.: gDLS: a scalable solution to the generalized pose and scale problem. In: European Conference on Computer Vision (ECCV) (2014)","DOI":"10.1007\/978-3-319-10593-2_2"},{"key":"1054_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0121-6","author":"T Weisser","year":"2016","unstructured":"Weisser, T., Lasserre, J.B., Toh, K.C.: A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Program. Comput. (MPC) (2016). https:\/\/doi.org\/10.1007\/s12532-017-0121-6","journal-title":"Math. Program. Comput. (MPC)"},{"key":"1054_CR40","doi-asserted-by":"crossref","unstructured":"Wilson, K., Bindel, D., Snavely, N.: When is rotations averaging hard? In: European Conference on Computer Vision (ECCV) (2016)","DOI":"10.1007\/978-3-319-46478-7_16"},{"key":"1054_CR41","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Kuang, Y., Sugimoto, S., Astrom, K., Okutomi, M.: Revisiting the PnP problem: a fast, general and optimal solution. In: International Conference on Computer Vision (ICCV) (2013)","DOI":"10.1109\/ICCV.2013.291"},{"issue":"2","key":"1054_CR42","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/17M1122025","volume":"28","author":"Y Zhong","year":"2018","unstructured":"Zhong, Y., Boumal, N.: Near-optimal bounds for phase synchronization. SIAM J. Opt. 28(2), 989\u20131016 (2018)","journal-title":"SIAM J. Opt."}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-021-01054-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-021-01054-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-021-01054-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:17:22Z","timestamp":1725891442000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-021-01054-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,7]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["1054"],"URL":"https:\/\/doi.org\/10.1007\/s10851-021-01054-y","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"value":"0924-9907","type":"print"},{"value":"1573-7683","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,7]]},"assertion":[{"value":"21 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}