{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T17:44:19Z","timestamp":1777657459258,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T00:00:00Z","timestamp":1631232000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T00:00:00Z","timestamp":1631232000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a general framework for solving the group synchronization problem, where we focus on the setting of adversarial or uniform corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios and consequently solve the synchronization problem in our setting. We first explain why the group cycle consistency information is essential for effectively solving group synchronization problems. We then establish exact recovery and linear convergence guarantees for the proposed message passing procedure under a deterministic setting with adversarial corruption. These guarantees hold as long as the ratio of corrupted cycles per edge is bounded by a reasonable constant. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further establish exact recovery with high probability under a common uniform corruption model.<\/jats:p>","DOI":"10.1007\/s10208-021-09532-w","type":"journal-article","created":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T14:02:23Z","timestamp":1631282543000},"page":"1665-1741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Robust Group Synchronization via Cycle-Edge Message Passing"],"prefix":"10.1007","volume":"22","author":[{"given":"Gilad","family":"Lerman","sequence":"first","affiliation":[]},{"given":"Yunpeng","family":"Shi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,10]]},"reference":[{"issue":"1","key":"9532_CR1","first-page":"6446","volume":"18","author":"E Abbe","year":"2017","unstructured":"Abbe, E.: Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research 18(1), 6446\u20136531 (2017)","journal-title":"The Journal of Machine Learning Research"},{"issue":"1","key":"9532_CR2","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/TNSE.2014.2368716","volume":"1","author":"E Abbe","year":"2014","unstructured":"Abbe, E., Bandeira, A.S., Bracher, A., Singer, A.: Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Trans. Network Science and Engineering 1(1), 10\u201322 (2014). 10.1109\/TNSE.2014.2368716","journal-title":"IEEE Trans. Network Science and Engineering"},{"key":"9532_CR3","doi-asserted-by":"crossref","unstructured":"Arie-Nachimson, M., Kovalsky, S.Z., Kemelmacher-Shlizerman, I., Singer, A., Basri, R.: Global motion estimation from point matches. In: 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission, Zurich, Switzerland, pp. 81\u201388 (2012). 10.1109\/3DIMPVT.2012.46","DOI":"10.1109\/3DIMPVT.2012.46"},{"issue":"4","key":"9532_CR4","doi-asserted-by":"publisher","first-page":"1963","DOI":"10.1137\/16M1060248","volume":"9","author":"F Arrigoni","year":"2016","unstructured":"Arrigoni, F., Rossi, B., Fusiello, A.: Spectral synchronization of multiple views in SE(3). SIAM J. Imaging Sci. 9(4), 1963\u20131990 (2016). 10.1137\/16M1060248. https:\/\/doi.org\/10.1137\/16M1060248","journal-title":"SIAM J. Imaging Sci."},{"issue":"2","key":"9532_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10208-016-9341-9","volume":"18","author":"AS Bandeira","year":"2018","unstructured":"Bandeira, A.S.: Random Laplacian matrices and convex relaxations. Foundations of Computational Mathematics 18(2), 345\u2013379 (2018). 10.1007\/s10208-016-9341-9","journal-title":"Foundations of Computational Mathematics"},{"issue":"1\u20132","key":"9532_CR6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10107-016-1059-6","volume":"163","author":"AS Bandeira","year":"2017","unstructured":"Bandeira, A.S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming 163(1-2), 145\u2013167 (2017)","journal-title":"Mathematical Programming"},{"issue":"6","key":"9532_CR7","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S1631-073X(02)02292-6","volume":"334","author":"O Bousquet","year":"2002","unstructured":"Bousquet, O.: A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334(6), 495\u2013500 (2002). 10.1016\/S1631-073X(02)02292-6","journal-title":"C. R. Math. Acad. Sci. Paris"},{"key":"9532_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, A., Govindu, V.M.: Efficient and robust large-scale rotation averaging. In: IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia, December 1-8, 2013, pp. 521\u2013528 (2013)","DOI":"10.1109\/ICCV.2013.70"},{"issue":"8","key":"9532_CR9","doi-asserted-by":"publisher","first-page":"1648","DOI":"10.1002\/cpa.21760","volume":"71","author":"Y Chen","year":"2018","unstructured":"Chen, Y., Cand\u00e8s, E.J.: The projected power method: an efficient algorithm for joint alignment from pairwise differences. Comm. Pure Appl. Math. 71(8), 1648\u20131714 (2018). 10.1002\/cpa.21760. https:\/\/doi-org.ezp3.lib.umn.edu\/10.1002\/cpa.21760","journal-title":"Comm. Pure Appl. Math."},{"key":"9532_CR10","unstructured":"Chen, Y., Guibas, L.J., Huang, Q.: Near-optimal joint object matching via convex relaxation. In: Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 100\u2013108 (2014)"},{"issue":"10","key":"9532_CR11","doi-asserted-by":"publisher","first-page":"5881","DOI":"10.1109\/TIT.2016.2600566","volume":"62","author":"Y Chen","year":"2016","unstructured":"Chen, Y., Suh, C., Goldsmith, A.J.: Information recovery from pairwise measurements. IEEE Trans. Inf. Theory 62(10), 5881\u20135905 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9532_CR12","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1093\/comnet\/cnu050","volume":"3","author":"M Cucuringu","year":"2015","unstructured":"Cucuringu, M.: Synchronization over Z2 and community detection in signed multiplex networks with constraints. J. Complex Networks 3(3), 469\u2013506 (2015)","journal-title":"J. Complex Networks"},{"key":"9532_CR13","doi-asserted-by":"crossref","unstructured":"Cucuringu, M., Lipman, Y., Singer, A.: Sensor network localization by eigenvector synchronization over the euclidean group. TOSN 8(3), 19:1\u201319:42 (2012)","DOI":"10.1145\/2240092.2240093"},{"issue":"45","key":"9532_CR14","doi-asserted-by":"publisher","first-page":"18914","DOI":"10.1073\/pnas.0909892106","volume":"106","author":"DL Donoho","year":"2009","unstructured":"Donoho, D.L., Maleki, A., Montanari, A.: Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences 106(45), 18914\u201318919 (2009). 10.1073\/pnas.0909892106","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"9532_CR15","unstructured":"Fan, Y., Zhao, Z.: Cryo-Electron Microscopy Image Analysis Using Multi-Frequency Vector Diffusion Maps. arXiv e-prints arXiv:1904.07772 (2019)"},{"key":"9532_CR16","unstructured":"Fan, Y., Zhao, Z.: Multi-frequency vector diffusion maps. In: Proceedings of the 36th International Conference on Machine Learning, vol.\u00a097, pp. 1843\u20131852. Long Beach, California, USA (2019)"},{"key":"9532_CR17","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47\u201363. ACM (1974)","DOI":"10.1145\/800119.803884"},{"issue":"6","key":"9532_CR18","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995). 10.1145\/227683.227684","journal-title":"J. ACM"},{"key":"9532_CR19","doi-asserted-by":"crossref","unstructured":"Govindu, V.M.: Lie-algebraic averaging for globally consistent motion estimation. In: 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2004), 27 June - 2 July 2004, Washington, DC, USA, pp. 684\u2013691 (2004)","DOI":"10.1109\/CVPR.2004.1315098"},{"issue":"1","key":"9532_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/cpa.21727","volume":"71","author":"P Hand","year":"2018","unstructured":"Hand, P., Lee, C., Voroninski, V.: Shapefit: Exact location recovery from corrupted pairwise directions. Communications on Pure and Applied Mathematics 71(1), 3\u201350 (2018)","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"9532_CR21","doi-asserted-by":"crossref","unstructured":"Hartley, R.I., Aftab, K., Trumpf, J.: L1 rotation averaging using the weiszfeld algorithm. In: The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20-25 June 2011, pp. 3041\u20133048 (2011)","DOI":"10.1109\/CVPR.2011.5995745"},{"issue":"5","key":"9532_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1111\/cgf.12184","volume":"32","author":"Q Huang","year":"2013","unstructured":"Huang, Q., Guibas, L.J.: Consistent shape maps via semidefinite programming. Comput. Graph. Forum 32(5), 177\u2013186 (2013)","journal-title":"Comput. Graph. Forum"},{"key":"9532_CR23","unstructured":"Huang, X., Liang, Z., Bajaj, C., Huang, Q.: Translation synchronization via truncated least squares. In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1459\u20131468 (2017)"},{"key":"9532_CR24","doi-asserted-by":"publisher","unstructured":"Huroyan, V., Lerman, G., Wu, H.T.: Solving jigsaw puzzles by the graph connection Laplacian. SIAM J. Imag. Sci. 13(4), 1717\u20131753 (2020). https:\/\/doi.org\/10.1137\/19M1290760","DOI":"10.1137\/19M1290760"},{"issue":"2","key":"9532_CR25","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10851-009-0161-2","volume":"35","author":"DQ Huynh","year":"2009","unstructured":"Huynh, D.Q.: Metrics for 3D rotations: comparison and analysis. J. Math. Imaging Vision 35(2), 155\u2013164 (2009). 10.1007\/s10851-009-0161-2","journal-title":"J. Math. Imaging Vision"},{"key":"9532_CR26","doi-asserted-by":"crossref","unstructured":"Koltchinskii, V.: Oracle inequalities in empirical risk minimization and sparse recovery problems, Lecture Notes in Mathematics, vol. 2033. Springer, Heidelberg (2011). 10.1007\/978-3-642-22147-7. Lectures from the 38th Probability Summer School held in Saint-Flour, 2008","DOI":"10.1007\/978-3-642-22147-7"},{"issue":"2","key":"9532_CR27","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s10208-014-9221-0","volume":"15","author":"G Lerman","year":"2015","unstructured":"Lerman, G., McCoy, M.B., Tropp, J.A., Zhang, T.: Robust computation of linear models by convex relaxation. Foundations of Computational Mathematics 15(2), 363\u2013410 (2015). 10.1007\/s10208-014-9221-0","journal-title":"Foundations of Computational Mathematics"},{"issue":"4","key":"9532_CR28","doi-asserted-by":"publisher","first-page":"2692","DOI":"10.1137\/17M115061X","volume":"11","author":"G Lerman","year":"2018","unstructured":"Lerman, G., Shi, Y., Zhang, T.: Exact camera location recovery by least unsquared deviations. SIAM J. Imaging Sciences 11(4), 2692\u20132721 (2018). 10.1137\/17M115061X","journal-title":"SIAM J. Imaging Sciences"},{"key":"9532_CR29","unstructured":"Ling, S.: Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods. arXiv preprint arXiv:2008.05341 (2020)"},{"key":"9532_CR30","doi-asserted-by":"crossref","unstructured":"Martinec, D., Pajdla, T.: Robust rotation and translation estimation in multiview reconstruction. In: 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007), 18-23 June 2007, Minneapolis, Minnesota, USA (2007)","DOI":"10.1109\/CVPR.2007.383115"},{"key":"9532_CR31","unstructured":"Mei, S., Misiakiewicz, T., Montanari, A., Oliveira, R.I.: Solving sdps for synchronization and maxcut problems via the grothendieck inequality. In: Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pp. 1476\u20131515 (2017)"},{"key":"9532_CR32","unstructured":"Montanari, A., Sen, S.: Semidefinite programs on sparse random graphs and their application to community detection. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pp. 814\u2013827 (2016)"},{"key":"9532_CR33","doi-asserted-by":"crossref","unstructured":"\u00d6zyesil, O., Singer, A.: Robust camera location estimation by convex programming. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pp. 2674\u20132683 (2015)","DOI":"10.1109\/CVPR.2015.7298883"},{"issue":"2","key":"9532_CR34","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1137\/140977576","volume":"8","author":"O \u00d6zyesil","year":"2015","unstructured":"\u00d6zyesil, O., Singer, A., Basri, R.: Stable camera motion estimation using convex programming. SIAM Journal on Imaging Sciences 8(2), 1220\u20131262 (2015)","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"9532_CR35","unstructured":"Pachauri, D., Kondor, R., Singh, V.: Solving the multi-way matching problem by permutation synchronization. In: Advances in Neural Information Processing Systems 26, pp. 1860\u20131868. Curran Associates, Inc. (2013)"},{"key":"9532_CR36","doi-asserted-by":"crossref","unstructured":"Perry, A., Wein, A.S., Bandeira, A.S., Moitra, A.: Message-passing algorithms for synchronization problems over compact groups. Communications on Pure and Applied Mathematics (2018)","DOI":"10.1002\/cpa.21750"},{"key":"9532_CR37","doi-asserted-by":"crossref","unstructured":"Shen, T., Zhu, S., Fang, T., Zhang, R., Quan, L.: Graph-based consistent matching for structure-from-motion. In: European Conference on Computer Vision, pp. 139\u2013155. Springer (2016)","DOI":"10.1007\/978-3-319-46487-9_9"},{"key":"9532_CR38","doi-asserted-by":"crossref","unstructured":"Shi, Y., Lerman, G.: Estimation of camera locations in highly corrupted scenarios: All about that base, no shape trouble. In: 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 2868\u20132876 (2018). 10.1109\/CVPR.2018.00303","DOI":"10.1109\/CVPR.2018.00303"},{"key":"9532_CR39","unstructured":"Shi, Y., Lerman, G.: Message passing least squares framework and its application to rotation synchronization. In: Proceedings of the 37th International Conference on Machine Learning (ICML) (2020)"},{"key":"9532_CR40","unstructured":"Shi, Y., Li, S., Lerman, G.: Robust multi-object matching via iterative reweighting of the graph connection Laplacian. In: Advances in Neural Information Processing Systems, vol.\u00a033, pp. 15243\u201315253. Curran Associates, Inc. (2020). https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/ae06fbdc519bddaa88aa1b24bace4500-Paper.pdf"},{"issue":"1","key":"9532_CR41","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.acha.2010.02.001","volume":"30","author":"A Singer","year":"2011","unstructured":"Singer, A.: Angular synchronization by eigenvectors and semidefinite programming. Applied and computational harmonic analysis 30(1), 20\u201336 (2011)","journal-title":"Applied and computational harmonic analysis"},{"key":"9532_CR42","doi-asserted-by":"crossref","unstructured":"Singer, A., Coifman, R., Sigworth, F., Chester, D., Y, S.: Detecting consistent common lines in cryo-em by voting. Journal of Structural Biology 169(3), 312\u2013322 (2010)","DOI":"10.1016\/j.jsb.2009.11.003"},{"issue":"2","key":"9532_CR43","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/090767777","volume":"4","author":"A Singer","year":"2011","unstructured":"Singer, A., Shkolnisky, Y.: Three-dimensional structure determination from common lines in cryo-em by eigenvectors and semidefinite programming. SIAM journal on imaging sciences 4(2), 543\u2013572 (2011)","journal-title":"SIAM journal on imaging sciences"},{"issue":"8","key":"9532_CR44","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1002\/cpa.21395","volume":"65","author":"A Singer","year":"2012","unstructured":"Singer, A., Wu, H.T.: Vector diffusion maps and the connection Laplacian. Comm. Pure Appl. Math. 65(8), 1067\u20131144 (2012). 10.1002\/cpa.21395","journal-title":"Comm. Pure Appl. Math."},{"key":"9532_CR45","doi-asserted-by":"crossref","unstructured":"Wang, L., Singer, A.: Exact and stable recovery of rotations for robust synchronization. Information and Inference (2013)","DOI":"10.1093\/imaiai\/iat005"},{"key":"9532_CR46","first-page":"236","volume":"8","author":"JS Yedidia","year":"2003","unstructured":"Yedidia, J.S., Freeman, W.T., Weiss, Y.: Understanding belief propagation and its generalizations. Exploring artificial intelligence in the new millennium 8, 236\u2013239 (2003)","journal-title":"Exploring artificial intelligence in the new millennium"},{"key":"9532_CR47","doi-asserted-by":"crossref","unstructured":"Zach, C., Klopschitz, M., Pollefeys, M.: Disambiguating visual relations using loop constraints. In: The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, USA, 13-18 June 2010, pp. 1426\u20131433 (2010)","DOI":"10.1109\/CVPR.2010.5539801"},{"issue":"1","key":"9532_CR48","first-page":"749","volume":"15","author":"T Zhang","year":"2014","unstructured":"Zhang, T., Lerman, G.: A novel M-estimator for robust PCA. Journal of Machine Learning Research 15(1), 749\u2013808 (2014)","journal-title":"Journal of Machine Learning Research"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09532-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09532-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09532-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T05:31:10Z","timestamp":1725773470000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09532-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,10]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9532"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09532-w","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,10]]},"assertion":[{"value":"8 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}