{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:55:43Z","timestamp":1743033343948,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031730207"},{"type":"electronic","value":"9783031730214"}],"license":[{"start":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T00:00:00Z","timestamp":1732147200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T00:00:00Z","timestamp":1732147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-73021-4_10","type":"book-chapter","created":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T09:18:15Z","timestamp":1732094295000},"page":"160-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Convex Relaxations for\u00a0Manifold-Valued Markov Random Fields with\u00a0Approximation Guarantees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8016-740X","authenticated-orcid":false,"given":"Robin","family":"Kenis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9106-2690","authenticated-orcid":false,"given":"Emanuel","family":"Laude","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4824-7697","authenticated-orcid":false,"given":"Panagiotis","family":"Patrinos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,21]]},"reference":[{"key":"10_CR1","unstructured":"ApS, M.: The MOSEK optimization toolbox for MATLAB manual. Version 10.1. (2024). http:\/\/docs.mosek.com\/latest\/toolbox\/index.html"},{"issue":"3","key":"10_CR2","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/21M1433241","volume":"15","author":"H Bauermeister","year":"2022","unstructured":"Bauermeister, H., Laude, E., M\u00f6llenhoff, T., Moeller, M., Cremers, D.: Lifting the convex conjugate in Lagrangian relaxations: a tractable approach for continuous Markov random fields. SIAM J. Imag. Sci. 15(3), 1253\u20131281 (2022)","journal-title":"SIAM J. Imag. Sci."},{"key":"10_CR3","doi-asserted-by":"publisher","unstructured":"Beinert, R., Bresch, J., Steidl, G.: Denoising of sphere- and SO(3)-valued data by relaxed tikhonov regularization. CoRR abs\/2307.10980 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2307.10980","DOI":"10.48550\/ARXIV.2307.10980"},{"key":"10_CR4","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/8579.001.0001","volume-title":"Markov Random Fields for Vision and Image Processing","author":"A Blake","year":"2011","unstructured":"Blake, A., Kohli, P., Rother, C.: Markov Random Fields for Vision and Image Processing. MIT Press, Cambridge (2011)"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, Philadelphia, PA (2012)","DOI":"10.1137\/1.9781611972290"},{"key":"10_CR6","unstructured":"Boumal, N., Mishra, B., Absil, P.A., Sepulchre, R.: Manopt, a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15(42), 1455\u20131459 (2014). https:\/\/www.manopt.org"},{"key":"10_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/9781009166164","volume-title":"An Introduction to Optimization on Smooth Manifolds","author":"N Boumal","year":"2023","unstructured":"Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge (2023)"},{"issue":"2","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1109\/LRA.2018.2793352","volume":"3","author":"L Carlone","year":"2018","unstructured":"Carlone, L., Calafiore, G.C.: Convex relaxations for pose graph optimization with outliers. IEEE Robot. Autom. Lett. 3(2), 1160\u20131167 (2018)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"2","key":"10_CR9","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1109\/TRO.2013.2291626","volume":"30","author":"L Carlone","year":"2014","unstructured":"Carlone, L., Censi, A.: From angular manifolds to the integer lattice: guaranteed orientation estimation with application to pose graph optimization. IEEE Trans. Rob. 30(2), 475\u2013492 (2014)","journal-title":"IEEE Trans. Rob."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"105456","DOI":"10.1016\/j.jat.2020.105456","volume":"258","author":"L Condat","year":"2020","unstructured":"Condat, L.: Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain. J. Approx. Theory 258, 105456 (2020)","journal-title":"J. Approx. Theory"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"2775","DOI":"10.1109\/TSP.2022.3179816","volume":"70","author":"L Condat","year":"2022","unstructured":"Condat, L.: Tikhonov regularization of circle-valued signals. IEEE Trans. Signal Process. 70, 2775\u20132782 (2022). https:\/\/doi.org\/10.1109\/TSP.2022.3179816","journal-title":"IEEE Trans. Signal Process."},{"key":"10_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-319-10578-9_18","volume-title":"Computer Vision \u2013 ECCV 2014","author":"A Fix","year":"2014","unstructured":"Fix, A., Agarwal, S.: Duality and the continuous graphical model. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds.) ECCV 2014. LNCS, vol. 8691, pp. 266\u2013281. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-10578-9_18"},{"issue":"4","key":"10_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1109\/MITS.2010.939925","volume":"2","author":"G Grisetti","year":"2010","unstructured":"Grisetti, G., K\u00fcmmerle, R., Stachniss, C., Burgard, W.: A tutorial on graph-based SLAM. IEEE Intell. Transp. Syst. Mag. 2(4), 31\u201343 (2010)","journal-title":"IEEE Intell. Transp. Syst. Mag."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Henrion, D., Korda, M., Lasserre, J.B.: The Moment-SOS Hierarchy, Optimization and its Applications, vol.\u00a04. World Scientific Publishing Europe Ltd. (2020)","DOI":"10.1142\/q0252"},{"issue":"9","key":"10_CR16","doi-asserted-by":"publisher","first-page":"2251","DOI":"10.1109\/TIP.2007.903257","volume":"16","author":"SH Kang","year":"2007","unstructured":"Kang, S.H., March, R.: Variational models for image colorization via chromaticity and brightness decomposition. IEEE Trans. Image Process. 16(9), 2251\u20132261 (2007)","journal-title":"IEEE Trans. Image Process."},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1287\/mnsc.6.4.366","volume":"6","author":"LV Kantorovich","year":"1960","unstructured":"Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manage. Sci. 6, 366\u2013422 (1960)","journal-title":"Manage. Sci."},{"issue":"2","key":"10_CR18","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J.H., et al.: A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115(2), 155\u2013184 (2015). https:\/\/doi.org\/10.1007\/s11263-015-0809-x","journal-title":"Int. J. Comput. Vis."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V.: Convergent tree-reweighted message passing for energy minimization. IEEE Trans. Pattern Anal. Mach. Intell. 28, 1568\u20131583 (2006). https:\/\/api.semanticscholar.org\/CorpusID:8616813","DOI":"10.1109\/TPAMI.2006.200"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V.: Solving relaxations of MAP-MRF problems: combinatorial in-face Frank-Wolfe directions. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 11980\u201311989 (2023)","DOI":"10.1109\/CVPR52729.2023.01153"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Komodakis, N., Paragios, N., Tziritas, G.: MRF optimization via dual decomposition: message-passing revisited. In: 2007 IEEE 11th International Conference on Computer Vision, pp.\u00a01\u20138 (2007)","DOI":"10.1109\/ICCV.2007.4408890"},{"issue":"3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/05064504X","volume":"17","author":"JB Lasserre","year":"2006","unstructured":"Lasserre, J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822\u2013843 (2006)","journal-title":"SIAM J. Optim."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (2004)","DOI":"10.1137\/S1052623400366802"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Laude, E., M\u00f6llenhoff, T., M\u00f6ller, M., Lellmann, J., Cremers, D.: Sublabel-accurate convex relaxation of vectorial multilabel energies. In: European Conference on Computer Vision (2016). https:\/\/api.semanticscholar.org\/CorpusID:6156695","DOI":"10.1007\/978-3-319-46448-0_37"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Lellmann, J., Strekalovskiy, E., Koetter, S., Cremers, D.: Total variation regularization for functions with values in a manifold. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2944\u20132951 (2013)","DOI":"10.1109\/ICCV.2013.366"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Mangelson, J.G., Liu, J., Eustice, R.M., Vasudevan, R.: Guaranteed globally optimal planar pose graph and landmark SLAM via sparse-bounded sums-of-squares programming. In: 2019 International Conference on Robotics and Automation (ICRA), pp. 9306\u20139312. IEEE (2019)","DOI":"10.1109\/ICRA.2019.8794454"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of 8th International Conference on Computer Vision, vol.\u00a02, pp. 416\u2013423 (2001)","DOI":"10.1109\/ICCV.2001.937655"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Mollenhoff, T., Cremers, D.: Sublabel-accurate discretization of nonconvex free-discontinuity problems. In: 2017 IEEE International Conference on Computer Vision (ICCV), pp. 1192\u20131200. IEEE Computer Society, Los Alamitos, CA, USA (2017)","DOI":"10.1109\/ICCV.2017.134"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Mollenhoff, T., Cremers, D.: Lifting vectorial variational problems: a natural formulation based on geometric measure theory and discrete exterior calculus. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 11117\u201311126 (2019)","DOI":"10.1109\/CVPR.2019.01137"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"4","key":"10_CR31","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/090757617","volume":"3","author":"T Pock","year":"2010","unstructured":"Pock, T., Cremers, D., Bischof, H., Chambolle, A.: Global solutions of variational models with convex regularization. SIAM J. Imag. Sci. 3(4), 1122\u20131145 (2010)","journal-title":"SIAM J. Imag. Sci."},{"key":"10_CR32","unstructured":"Rabiner, L., Juang, B.H.: Fundamentals of Speech Recognition. Englewood Cliffs (1993)"},{"issue":"1","key":"10_CR33","doi-asserted-by":"publisher","first-page":"167","DOI":"10.2140\/pjm.1967.21.167","volume":"21","author":"R Rockafellar","year":"1967","unstructured":"Rockafellar, R.: Duality and stability in extremum problems involving convex functions. Pac. J. Math. 21(1), 167\u2013187 (1967)","journal-title":"Pac. J. Math."},{"issue":"1","key":"10_CR34","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","volume":"60","author":"LI Rudin","year":"1992","unstructured":"Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1), 259\u2013268 (1992)","journal-title":"Physica D"},{"key":"10_CR35","doi-asserted-by":"crossref","unstructured":"Santambrogio, F.: Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling, vol.\u00a087. Birkh\u00e4user (2015)","DOI":"10.1007\/978-3-319-20828-2"},{"key":"10_CR36","doi-asserted-by":"publisher","unstructured":"Savchynskyy, B.: Discrete graphical models \u2014 an optimization perspective. Found. Trends\u00ae Comput. Graph. Vis. 11(3-4), 160\u2013429 (2019). https:\/\/doi.org\/10.1561\/0600000084","DOI":"10.1561\/0600000084"},{"key":"10_CR37","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-030-31351-7_3","volume-title":"Handbook of Variational Methods for Nonlinear Geometric Data","author":"T Vogt","year":"2020","unstructured":"Vogt, T., Strekalovskiy, E., Cremers, D., Lellmann, J.: Lifting methods for manifold-valued variational problems. In: Grohs, P., Holler, M., Weinmann, A. (eds.) Handbook of Variational Methods for Nonlinear Geometric Data, pp. 95\u2013119. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-31351-7_3"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Found. Trends\u00ae Mach. Learn. 1(1\u20132), 1\u2013305 (2008)","DOI":"10.1561\/2200000001"},{"issue":"1","key":"10_CR39","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/050623802","volume":"17","author":"H Waki","year":"2006","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"10_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-017-0121-6","volume":"10","author":"T Weisser","year":"2018","unstructured":"Weisser, T., Lasserre, J.B., Toh, K.C.: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Program. Comput. 10(1), 1\u201332 (2018)","journal-title":"Math. Program. Comput."},{"key":"10_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/978-3-319-46475-6_52","volume-title":"Computer Vision \u2013 ECCV 2016","author":"T Windheuser","year":"2016","unstructured":"Windheuser, T., Cremers, D.: A convex solution to spatially-regularized correspondence problems. In: Leibe, B., Matas, J., Sebe, N., Welling, M. (eds.) ECCV 2016. LNCS, vol. 9906, pp. 853\u2013868. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46475-6_52"},{"key":"10_CR42","unstructured":"Yang, H., Carlone, L.: One ring to rule them all: certifiably robust geometric perception with outliers. In: Advance in Neural Information Processing System, vol. 33, pp. 18846\u201318859 (2020)"}],"container-title":["Lecture Notes in Computer Science","Computer Vision \u2013 ECCV 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-73021-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T09:43:17Z","timestamp":1732095797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-73021-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,21]]},"ISBN":["9783031730207","9783031730214"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-73021-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,21]]},"assertion":[{"value":"21 November 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECCV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Computer Vision","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eccv2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eccv2024.ecva.net\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}