{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T15:08:33Z","timestamp":1779116913018,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T00:00:00Z","timestamp":1770940800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T00:00:00Z","timestamp":1770940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["403056140"],"award-info":[{"award-number":["403056140"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Entropic optimal transport has become a popular tool in data analysis and it can be solved efficiently with the celebrated Sinkhorn algorithm, but large scale problems remain challenging. Domain decomposition has been shown to be an efficient strategy on large grids. Unbalanced optimal transport is a versatile generalization of the standard (balanced) optimal transport problem and its entropic variant can also be solved with a generalized Sinkhorn algorithm. However, the domain decomposition algorithm cannot be applied directly to the unbalanced problem since independence of the cell problems is lost. In this article we generalize the domain decomposition algorithm for optimal transport to the unbalanced setting by introducing a new adaptive step size strategy, which allows to ensure the decrement of the global score and prove convergence to the global minimizer. We also provide an efficient GPU implementation of the new algorithm and demonstrate with experiments that domain decomposition is also an efficient strategy for large unbalanced optimal transport problems.<\/jats:p>","DOI":"10.1007\/s10589-025-00748-y","type":"journal-article","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T09:30:25Z","timestamp":1770975025000},"page":"279-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Domain decomposition for entropic unbalanced optimal transport"],"prefix":"10.1007","volume":"94","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2945-5792","authenticated-orcid":false,"given":"Ismael","family":"Medina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"The Sang","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Schmitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"748_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-71050-9","volume-title":"Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften","author":"C Villani","year":"2009","unstructured":"Villani, C.: Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften, vol. 338. Springer, Berlin (2009)"},{"key":"748_CR2","volume-title":"Optimal Transport for Applied Mathematicians. Progress in Nonlinear Differential Equations and Their Applications","author":"F Santambrogio","year":"2015","unstructured":"Santambrogio, F.: Optimal Transport for Applied Mathematicians. Progress in Nonlinear Differential Equations and Their Applications, vol. 87. Birkh\u00e4user, Boston (2015)"},{"issue":"5\u20136","key":"748_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019). https:\/\/doi.org\/10.1561\/2200000073","journal-title":"Found. Trends Mach. Learn."},{"key":"748_CR4","unstructured":"Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transportation distances. In: Advances in Neural Information Processing Systems 26 (NIPS 2013), pp. 2292\u20132300 (2013)"},{"key":"748_CR5","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/s00211-020-01127-x","volume":"145","author":"RJ Berman","year":"2020","unstructured":"Berman, R.J.: The Sinkhorn algorithm, parabolic optimal transport and geometric Monge\u2013Amp\u00e8re equations. Numer. Math. 145, 771\u2013836 (2020). https:\/\/doi.org\/10.1007\/s00211-020-01127-x","journal-title":"Numer. Math."},{"key":"748_CR6","doi-asserted-by":"crossref","unstructured":"Solomon, J., Goes, F., Peyr\u00e9, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., Guibas, L.: Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graphics (Proc. of SIGGRAPH 2015) 34(4), 66\u201316611 (2015)","DOI":"10.1145\/2766963"},{"issue":"1","key":"748_CR7","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1214\/aoms\/1177697802","volume":"40","author":"RM Dudley","year":"1969","unstructured":"Dudley, R.M.: The Speed of Mean Glivenko\u2013Cantelli Convergence. Ann. Math. Stat. 40(1), 40\u201350 (1969). https:\/\/doi.org\/10.1214\/aoms\/1177697802","journal-title":"Ann. Math. Stat."},{"key":"748_CR8","unstructured":"Genevay, A., Chizat, L., Bach, F., Cuturi, M., Peyr\u00e9, G.: Sample complexity of sinkhorn divergences. In: Proceedings of the 22nd International Conference on AI and Statistics (AISTATS\u201919) (2019). https:\/\/arxiv.org\/abs\/1810.02733"},{"key":"748_CR9","unstructured":"Feydy, J., S\u00e9journ\u00e9, T., Vialard, F.-X., Amari, S.-i., Trouve, A., Peyr\u00e9, G.: Interpolating between optimal transport and MMD using Sinkhorn divergences. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2681\u20132690 (2019)"},{"key":"748_CR10","unstructured":"Bunne, C., Meng-Papaxanthos, L., Krause, A., Cuturi, M.: Proximal optimal transport modeling of population dynamics. In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151, pp. 6511\u20136528 (2021)"},{"key":"748_CR11","unstructured":"Lavenant, H., Zhang, S., Kim, Y.-H., Schiebinger, G.: Towards a mathematical theory of trajectory inference. arXiv:2102.09204 (2021)"},{"issue":"4","key":"748_CR12","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1016\/j.cell.2019.01.006","volume":"176","author":"G Schiebinger","year":"2019","unstructured":"Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., Lee, L., Chen, J., Brumbaugh, J., Rigollet, P., Hochedlinger, K., Jaenisch, R., Regev, A., Lander, E.S.: Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell 176(4), 928\u201394322 (2019). https:\/\/doi.org\/10.1016\/j.cell.2019.01.006","journal-title":"Cell"},{"issue":"8","key":"748_CR13","doi-asserted-by":"publisher","first-page":"2169","DOI":"10.1093\/bioinformatics\/btac084","volume":"38","author":"G-J Huizing","year":"2022","unstructured":"Huizing, G.-J., Peyr\u00e9, G., Cantini, L.: Optimal transport improves cell-cell similarity inference in single-cell omics data. Bioinformatics 38(8), 2169\u20132177 (2022). https:\/\/doi.org\/10.1093\/bioinformatics\/btac084","journal-title":"Bioinformatics"},{"issue":"1","key":"748_CR14","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1038\/s43586-024-00334-2","volume":"4","author":"C Bunne","year":"2024","unstructured":"Bunne, C., Schiebinger, G., Krause, A., Regev, A., Cuturi, M.: Optimal transport for single-cell and spatial omics. Nature Rev. Methods Primers 4(1), 58 (2024)","journal-title":"Nature Rev. Methods Primers"},{"key":"748_CR15","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/s11263-012-0566-z","volume":"101","author":"W Wang","year":"2012","unstructured":"Wang, W., Slep\u010dev, D., Basu, S., Ozolek, J.A., Rohde, G.K.: A linear optimal transportation framework for quantifying and visualizing variations in sets of images. Int. J. Comput. Vision 101, 254\u2013269 (2012). https:\/\/doi.org\/10.1007\/s11263-012-0566-z","journal-title":"Int. J. Comput. Vision"},{"key":"748_CR16","doi-asserted-by":"publisher","unstructured":"Tameling, C., Stoldt, S., Stephan, T., Naas, J., Jakobs, S., Munk, A.: Colocalization for super-resolution microscopy via optimal transport. Nat Comput Sci, 199\u2013211 (2021). https:\/\/doi.org\/10.1038\/s43588-021-00050-x","DOI":"10.1038\/s43588-021-00050-x"},{"issue":"5","key":"748_CR17","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.1109\/TMI.2019.2953773","volume":"39","author":"B Schmitzer","year":"2020","unstructured":"Schmitzer, B., Sch\u00e4fers, K.P., Wirth, B.: Dynamic cell imaging in PET with optimal transport regularization. IEEE Trans. Med. Imaging 39(5), 1626\u20131635 (2020). https:\/\/doi.org\/10.1109\/TMI.2019.2953773","journal-title":"IEEE Trans. Med. Imaging"},{"key":"748_CR18","unstructured":"Frogner, C., Zhang, C., Mobahi, H., Araya-Polo, M., Poggio, T.: Learning with a Wasserstein loss. Advances in Neural Information Processing Systems 28 (NIPS 2015) (2015)"},{"issue":"11","key":"748_CR19","doi-asserted-by":"publisher","first-page":"3090","DOI":"10.1016\/j.jfa.2018.03.008","volume":"274","author":"L Chizat","year":"2018","unstructured":"Chizat, L., Peyr\u00e9, G., Schmitzer, B., Vialard, F.-X.: Unbalanced optimal transport: dynamic and Kantorovich formulations. J. Funct. Anal. 274(11), 3090\u20133123 (2018). https:\/\/doi.org\/10.1016\/j.jfa.2018.03.008","journal-title":"J. Funct. Anal."},{"issue":"3","key":"748_CR20","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00222-017-0759-8","volume":"211","author":"M Liero","year":"2018","unstructured":"Liero, M., Mielke, A., Savar\u00e9, G.: Optimal entropy-transport problems and a new Hellinger\u2013Kantorovich distance between positive measures. Invent. Math. 211(3), 969\u20131117 (2018). https:\/\/doi.org\/10.1007\/s00222-017-0759-8","journal-title":"Invent. Math."},{"key":"748_CR21","doi-asserted-by":"publisher","unstructured":"Chizat, L., Peyr\u00e9, G., Schmitzer, B., Vialard, F.-X.: Scaling algorithms for unbalanced transport problems. Mathematics of Computation 87 (2016). https:\/\/doi.org\/10.1090\/mcom\/3303","DOI":"10.1090\/mcom\/3303"},{"issue":"4","key":"748_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.patter.2023.100714","volume":"4","author":"F Wu","year":"2023","unstructured":"Wu, F., Courty, N., Jin, S., Li, S.Z.: Improving molecular representation learning with metric learning-enhanced optimal transport. Patterns 4(4), 100714 (2023). https:\/\/doi.org\/10.1016\/j.patter.2023.100714","journal-title":"Patterns"},{"issue":"2","key":"748_CR23","doi-asserted-by":"publisher","first-page":"3404","DOI":"10.1109\/lra.2022.3147326","volume":"7","author":"B Besic","year":"2022","unstructured":"Besic, B., Gosala, N., Cattaneo, D., Valada, A.: Unsupervised domain adaptation for lidar panoptic segmentation. IEEE Robot. Autom. Lett. 7(2), 3404\u20133411 (2022). https:\/\/doi.org\/10.1109\/lra.2022.3147326","journal-title":"IEEE Robot. Autom. Lett."},{"key":"748_CR24","unstructured":"Chizat, L., Bach, F.: On the global convergence of gradient descent for over-parameterized models using optimal transport. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 31. Curran Associates, Inc., Montreal (2018). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2018\/file\/a1afc58c6ca9540d057299ec3016d726-Paper.pdf"},{"key":"748_CR25","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00211-021-01245-0","volume":"149","author":"M Bonafini","year":"2021","unstructured":"Bonafini, M., Schmitzer, B.: Domain decomposition for entropy regularized optimal transport. Numer. Math. 149, 819\u2013870 (2021). https:\/\/doi.org\/10.1007\/s00211-021-01245-0","journal-title":"Numer. Math."},{"issue":"6","key":"748_CR26","doi-asserted-by":"publisher","first-page":"1808","DOI":"10.1137\/0732082","volume":"32","author":"J-D Benamou","year":"1994","unstructured":"Benamou, J.-D.: A domain decomposition method for the polar factorization of vector-valued mappings. SIAM J. Numer. Anal. 32(6), 1808\u20131838 (1994)","journal-title":"SIAM J. Numer. Anal."},{"key":"748_CR27","unstructured":"Bonafini, M., Medina, I., Schmitzer, B.: Asymptotic analysis of domain decomposition for optimal transport (arXiv v1 version) (2021)"},{"key":"748_CR28","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/2025022","author":"I Medina","year":"2025","unstructured":"Medina, I., Schmitzer, B.: Flow updates for domain decomposition of entropic optimal transport. EDP Sci. (2025). https:\/\/doi.org\/10.1051\/m2an\/2025022","journal-title":"EDP Sci."},{"issue":"3","key":"748_CR29","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/s10851-022-01126-7","volume":"65","author":"F Beier","year":"2023","unstructured":"Beier, F., Lindheim, J., Neumayer, S., Steidl, G.: Unbalanced multi-marginal optimal transport. J. Math. Imaging Vis. 65(3), 394\u2013413 (2023). https:\/\/doi.org\/10.1007\/s10851-022-01126-7","journal-title":"J. Math. Imaging Vis."},{"issue":"1","key":"748_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-016-9331-y","volume":"18","author":"L Chizat","year":"2018","unstructured":"Chizat, L., Peyr\u00e9, G., Schmitzer, B., Vialard, F.-X.: An interpolating distance between optimal transport and fisher-rao metrics. Found. Comput. Math. 18(1), 1\u201344 (2018). https:\/\/doi.org\/10.1007\/s10208-016-9331-y","journal-title":"Found. Comput. Math."},{"issue":"3","key":"748_CR31","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/16M1106018","volume":"41","author":"B Schmitzer","year":"2019","unstructured":"Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM J. Sci. Comput. 41(3), 1443\u20131481 (2019). https:\/\/doi.org\/10.1137\/16M1106018","journal-title":"SIAM J. Sci. Comput."},{"key":"748_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-06409-2","volume-title":"Convex Analysis and Minimization Algorithms II","author":"J-B Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1993)"},{"key":"748_CR33","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00211-023-01347-x","volume":"153","author":"M Bonafini","year":"2023","unstructured":"Bonafini, M., Medina, I., Schmitzer, B.: Asymptotic analysis of domain decomposition for optimal transport. Numer. Math. 153, 451\u2013492 (2023). https:\/\/doi.org\/10.1007\/s00211-023-01347-x","journal-title":"Numer. Math."},{"key":"748_CR34","unstructured":"Feydy, J.: Geometric data analysis, beyond convolutions. Ph.D. thesis, Universit\u00e9 Paris-Saclay (2020)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00748-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-025-00748-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00748-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T14:32:40Z","timestamp":1779114760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-025-00748-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,13]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["748"],"URL":"https:\/\/doi.org\/10.1007\/s10589-025-00748-y","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,13]]},"assertion":[{"value":"18 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2026","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This article was originally published under the subscription model but it is now published under an Open Access license.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}