{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T08:40:15Z","timestamp":1771576815263,"version":"3.50.1"},"reference-count":57,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"German Federal Ministry of Education and Research BMBF 01|S20053B project SA\u2113E","award":["495365311"],"award-info":[{"award-number":["495365311"]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation DFG","doi-asserted-by":"publisher","award":["495365311"],"award-info":[{"award-number":["495365311"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix\u2013vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.<\/jats:p>","DOI":"10.3390\/a15090311","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T21:25:18Z","timestamp":1661894718000},"page":"311","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9710-9744","authenticated-orcid":false,"given":"Fatima Antarou","family":"Ba","sequence":"first","affiliation":[{"name":"Institute of Mathematics, Technische Universit\u00e4t Berlin, Stra\u00dfe des 17. Juni 136, 10623 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6206-5705","authenticated-orcid":false,"given":"Michael","family":"Quellmalz","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Technische Universit\u00e4t Berlin, Stra\u00dfe des 17. Juni 136, 10623 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","article-title":"Computational Optimal Transport: With Applications to Data Science","volume":"11","author":"Cuturi","year":"2019","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Villani, C. (2009). Optimal Transport: Old and New, Springer.","DOI":"10.1007\/978-3-540-71050-9"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Beier, F., von Lindheim, J., Neumayer, S., and Steidl, G. (2021). Unbalanced multi-marginal optimal transport. arXiv.","DOI":"10.1007\/s10851-022-01126-7"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/2897824.2925918","article-title":"Wasserstein barycentric coordinates: Histogram regression using optimal transport","volume":"35","author":"Bonneel","year":"2016","journal-title":"ACM Trans. Graph."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1726","DOI":"10.1137\/16M1067494","article-title":"Wasserstein loss for image synthesis and restoration","volume":"9","author":"Tartavel","year":"2016","journal-title":"SIAM J. Imaging Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10851-017-0726-4","article-title":"A transportation Lp distance for signal analysis","volume":"59","author":"Thorpe","year":"2017","journal-title":"J. Math. Imaging Vis."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1482","DOI":"10.1007\/s10851-018-0827-8","article-title":"Measure-valued variational models with applications to diffusion-weighted imaging","volume":"60","author":"Vogt","year":"2018","journal-title":"J. Math. Imaging Vis."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1621","DOI":"10.1051\/m2an\/2015033","article-title":"Numerical methods for matching for teams and Wasserstein barycenters","volume":"49","author":"Carlier","year":"2015","journal-title":"ESAIM M2AN"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Galichon, A. (2016). Optimal Transport Methods in Economics, Princeton University Press.","DOI":"10.23943\/princeton\/9780691172767.001.0001"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00440-013-0531-y","article-title":"Martingale optimal transport and robust hedging in continuous time","volume":"160","author":"Dolinsky","year":"2014","journal-title":"Probab. Theory Relat. Fields"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s00780-014-0227-x","article-title":"Robust hedging with proportional transaction costs","volume":"18","author":"Dolinsky","year":"2014","journal-title":"Financ. Stoch."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1038\/417260a","article-title":"A reconstruction of the initial conditions of the universe by optimal mass transportation","volume":"417","author":"Frisch","year":"2002","journal-title":"Nature"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2428","DOI":"10.1137\/20M1320195","article-title":"Multimarginal optimal transport with a tree-structured cost and the Schr\u00f6dinger bridge problem","volume":"59","author":"Haasler","year":"2021","journal-title":"SIAM J. Control Optim."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.5.1.1","article-title":"On the translocation of masses","volume":"5","author":"Kantorovich","year":"1958","journal-title":"Manag. Sci."},{"key":"ref_15","first-page":"1","article-title":"On the complexity of approximating multimarginal optimal transport","volume":"23","author":"Lin","year":"2022","journal-title":"J. Mach. Learn. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.3934\/dcds.2014.34.1623","article-title":"Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions","volume":"34","author":"Pass","year":"2014","journal-title":"Discret. Contin. Dyn. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1771","DOI":"10.1051\/m2an\/2015020","article-title":"Multi-marginal optimal transport: Theory and applications","volume":"49","author":"Pass","year":"2015","journal-title":"ESAIM M2AN"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Benamou, J.-D., Carlier, G., and Nenna, L. (2016). A numerical method to solve multi-marginal optimal transport problems with Coulomb cost. Splitting Methods in Communication, Imaging, Science, and Engineering, Springer.","DOI":"10.1007\/978-3-319-41589-5_17"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chen, K., Sch\u00f6nlieb, C.-B., Tai, X.-C., and Younces, L. (2021). From optimal transport to discrepancy. Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging: Mathematical Imaging and Vision, Springer.","DOI":"10.1007\/978-3-030-03009-4"},{"key":"ref_20","unstructured":"Terj\u00e9k, D., and Gonz\u00e1lez-S\u00e1nchez, D. (2021). Optimal transport with f-divergence regularization and generalized Sinkhorn algorithm. arXiv."},{"key":"ref_21","unstructured":"Blondel, M., Seguy, V., and Rolet, A. (2018, January 9\u201311). Smooth and sparse optimal transport. Proceedings of Machine Learning Research, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, Playa Blanca, Spain."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1007\/s00245-019-09614-w","article-title":"Quadratically regularized optimal transport","volume":"83","author":"Lorenz","year":"2021","journal-title":"Appl. Math. Optim."},{"key":"ref_23","unstructured":"Genevay, A., Cuturi, M., Peyr\u00e9, G., and Bach, F. (2016, January 5\u201310). Stochastic optimization for large-scale optimal transport. Proceedings of the 30th International Conference on Neural Information Processing Systems, Barcelona, Spain."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1137\/130926717","article-title":"Backpropagation imaging in nonlinear harmonic holography in the presence of measurement and medium noises","volume":"7","author":"Ammari","year":"2014","journal-title":"SIAM J. Imaging Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Altschuler, J.M., and Boix-Adsera, E. (2022). Polynomial-time algorithms for multimarginal optimal transport problems with structure. Math. Program., in press.","DOI":"10.1007\/s10107-022-01868-7"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"A1111","DOI":"10.1137\/141000439","article-title":"Iterative bregman projections for regularized transportation problems","volume":"37","author":"Benamou","year":"2015","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_27","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, The MIT Press. Adaptive Computation and Machine Learning."},{"key":"ref_28","unstructured":"Alaya, M.Z., B\u00e9rar, M., Gasso, G., and Rakotomamonjy, A. (2019, January 8\u201314). Screening Sinkhorn algorithm for regularized optimal transport. Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_29","unstructured":"Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K.Q. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, Curran Associates, Inc."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning connegative matrices and doubly stochastic matrices","volume":"21","author":"Knopp","year":"1967","journal-title":"Pac. J. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2013","DOI":"10.1137\/S1064827502400984","article-title":"Fast summation at nonequispaced knots by NFFTs","volume":"24","author":"Potts","year":"2003","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s00211-004-0538-5","article-title":"Fast convolution with radial kernels at nonequispaced knots","volume":"98","author":"Potts","year":"2004","journal-title":"Numer. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.jcp.2014.12.052","article-title":"Fast Ewald summation based on NFFT with mixed periodicity","volume":"285","author":"Nestler","year":"2015","journal-title":"J. Comput. Phys."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"085001","DOI":"10.1088\/0266-5611\/31\/8\/085001","article-title":"Optimal mollifiers for spherical deconvolution","volume":"31","author":"Hielscher","year":"2015","journal-title":"Inverse Probl."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3389\/fams.2018.00061","article-title":"NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks","volume":"4","author":"Alfke","year":"2018","journal-title":"Front. Appl. Math. Stat."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Lakshmanan, R., Pichler, A., and Potts, D. (2022). Fast Fourier transform boost for the Sinkhorn algorithm. arXiv.","DOI":"10.1553\/etna_vol58s289"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2766963","article-title":"Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains","volume":"34","author":"Solomon","year":"2015","journal-title":"ACM Trans. Graph."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Str\u00f6ssner, C., and Kressner, D. (2022). Low-rank tensor approximations for solving multi-marginal optimal transport problems. arXiv.","DOI":"10.1137\/22M1478355"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00211-018-0995-x","article-title":"Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm","volume":"142","author":"Benamou","year":"2019","journal-title":"Numer. Math."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"151","DOI":"10.4064\/sm209-2-4","article-title":"A general duality theorem for the Monge-Kantorovich transport problem","volume":"209","author":"Schachermayer","year":"2012","journal-title":"Studia Math."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"107474","DOI":"10.1016\/j.sigpro.2020.107474","article-title":"Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion","volume":"171","author":"Elvander","year":"2020","journal-title":"Signal Process."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s10915-020-01325-7","article-title":"An optimal transport approach for the Schr\u00f6dinger bridge problem and convergence of Sinkhorn algorithm","volume":"85","author":"Marino","year":"2020","journal-title":"J. Sci. Comput."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Plonka, G., Potts, D., Steidl, G., and Tasche, M. (2018). Numerical Fourier Analysis, Birkh\u00e4user. Applied and Numerical Harmonic Analysis.","DOI":"10.1007\/978-3-030-04306-3"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/acha.1995.1007","article-title":"Fast Fourier transforms for nonequispaced data II","volume":"2","author":"Dutt","year":"1995","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1006\/acha.1995.1026","article-title":"On the fast Fourier transform of functions with singularities","volume":"2","author":"Beylkin","year":"1995","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1555386.1555388","article-title":"Using NFFT3\u2014A software library for various nonequispaced fast Fourier transforms","volume":"36","author":"Keiner","year":"2009","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"28","DOI":"10.3389\/fphy.2016.00028","article-title":"Parameter tuning for the NFFT based fast Ewald summation","volume":"4","author":"Nestler","year":"2016","journal-title":"Front. Phys."},{"key":"ref_48","unstructured":"Bassetti, F., Gualandi, S., and Veneroni, M. (2018). On the computation of Kantorovich-Wasserstein distances between 2d-histograms by uncapacitated minimum cost flows. arXiv."},{"key":"ref_49","unstructured":"Cuturi, M., and Doucet, A. (2014, January 21\u201326). Fast computation of wasserstein barycenters. Proceedings of the 31st International Conference on International Conference on Machine Learning, Beijing, China."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Bruckstein, A.M., Romeny, B.M.t.H., Bronstein, A.M., and Bronstein, M.M. (2012). Wasserstein barycenter and its application to texture mixing. Scale Space and Variational Methods in Computer Vision, Springer.","DOI":"10.1007\/978-3-642-24785-9"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"von Lindheim, J. (2022). Approximative algorithms for multi-marginal optimal transport and free-support Wasserstein barycenters. arXiv.","DOI":"10.1007\/s10589-023-00458-3"},{"key":"ref_52","unstructured":"Takezawa, Y., Sato, R., Kozareva, Z., Ravi, S., and Yamada, M. (2021). Fixed support tree-sliced Wasserstein barycenter. arXiv."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1137\/100805741","article-title":"Barycenters in the Wasserstein space","volume":"43","author":"Agueh","year":"2011","journal-title":"SIAM J. Math. Anal."},{"key":"ref_54","first-page":"1","article-title":"Pot: Python optimal transport","volume":"22","author":"Flamary","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1090\/S0894-0347-1989-0969419-8","article-title":"The least action principle and the related concept of generalized flows for incompressible perfect fluids","volume":"2","author":"Brenier","year":"1989","journal-title":"J. Amer. Math. Soc."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF00375139","article-title":"The dual least action problem for an ideal, incompressible fluid","volume":"122","author":"Brenier","year":"1993","journal-title":"Arch. Ration. Mech. Anal."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/(SICI)1097-0312(199904)52:4<411::AID-CPA1>3.0.CO;2-3","article-title":"Minimal geodesics on groups of volume-preserving maps and generalized solutions of the euler equations","volume":"52","author":"Brenier","year":"1997","journal-title":"Comm. Pure Appl. Math"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/9\/311\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:20:06Z","timestamp":1760142006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/9\/311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,30]]},"references-count":57,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,9]]}},"alternative-id":["a15090311"],"URL":"https:\/\/doi.org\/10.3390\/a15090311","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,30]]}}}