[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

We address the numerical solution to multimarginal optimal transport (MMOT) with pairwise costs. MMOT, as a natural extension from the classical two-marginal optimal transport, has many important applications including image processing, density functional theory and machine learning, but lacks efficient and exact numerical methods. The popular entropy-regularized method may suffer numerical instability and blurring issues. Inspired by the back-and-forth method introduced by Jacobs and Léger, we investigate MMOT problems with pairwise costs. We show that such problems have a graphical representation and leverage this structure to develop a new computationally gradient ascent algorithm to solve the dual formulation of such MMOT problems. Our method produces accurate solutions which can be used for the regularization-free applications, including the computation of Wasserstein barycenters with high resolution imagery.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data Availability

All data sets and numerical results are publicly available via [27, 49].

Notes

  1. We distinguish between the projection of measures and the canonical projection of measures. For example, given a probability measure P on the space \((X_1\times X_2)\times X_3\cdots \times X_m\), then the projection of measures \((\pi _1)_{\#}P=P_{1}\in \mathbb {P}(X_1), (\pi _2)_{\#}P=P_2\in \mathbb {P}(X_2)\), while the canonical projection of measures \(({\textbf {Proj}}_1)_{\#}P=P_{12}\in \mathbb {P}(X_1\times X_2), ({\textbf {Proj}}_2)_{\#}P=P_3\in \mathbb {P}(X_3)\). This will be used in Lemma 3.2.

  2. To distinguish with the Legendre transform, we still denote the optimal solution to (2.3) by \((f_1,f_2)\).

  3. We adopt the terminology that the MMOT problem itself admits a graph structure, rather than saying that the cost function has a graph structure, which is the terminology used in [35, 36]. This distinction prevents confusion from the branched optimal transport problem (see e.g., [11, 45, 60]).

References

  1. Agueh, M., Carlier, G.: Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43, 904–924 (2011). https://doi.org/10.1137/100805741

    Article  MathSciNet  Google Scholar 

  2. Altschuler, J., Boix-Adserà, E.: Hardness results for multimarginal optimal transport problems. Discrete Optim. 42, 100669 (2021). https://doi.org/10.1016/j.disopt.2021.100669

    Article  MathSciNet  Google Scholar 

  3. Altschuler, J., Boix-Adserà, E.: Polynomial-time algorithms for multimarginal optimal transport problems with structure. Math. Program. (2022). https://doi.org/10.1007/s10107-022-01868-7

    Article  Google Scholar 

  4. Ambrosio, L., Brué, E., Semola, D.: Lectures on optimal transport, vol. 130 of Unitext. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72162-6. La Matematica per il 3+2

  5. Ambrosio, L., Gigli, N.: A user’s guide to optimal transport, in Modelling and optimisation of flows on networks, vol. 2062 of Lecture Notes in Mathematics, pp. 1–155. Springer, New York (2013). https://doi.org/10.1007/978-3-642-32160-3_1

  6. Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics, 2nd edn. ETH Zürich, Birkhäuser, Basel (2008)

    Google Scholar 

  7. Arjovsky, M., Chintala, S., Bottou, L.: Wasserstein generative adversarial networks. In: International Conference on Machine Learning, PMLR, pp. 214–223 (2017)

  8. Benamou, J., Brenier, Y.: A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem. Numer. Math. 84, 375–393 (2000). https://doi.org/10.1007/s002110050002

    Article  MathSciNet  Google Scholar 

  9. Benamou, J., Carlier, G., Cuturi, M., Nenna, L., Peyré, G.: Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37, A1111–A1138 (2015). https://doi.org/10.1137/141000439

    Article  MathSciNet  Google Scholar 

  10. Benamou, J., Froese, B.D., Oberman, A.M.: Numerical solution of the optimal transportation problem using the Monge–Ampère equation. J. Comput. Phys. 260, 107–126 (2014). https://doi.org/10.1016/j.jcp.2013.12.015

    Article  MathSciNet  Google Scholar 

  11. Bernot, M., Caselles, V., Morel, J.-M.: The structure of branched transportation networks. Calc. Var. Partial Differ. Equ. 32, 279–317 (2008). https://doi.org/10.1007/s00526-007-0139-0

    Article  MathSciNet  Google Scholar 

  12. Brenier, Y.: The least action principle and the related concept of generalized flows for incompressible perfect fluids. J. Am. Math. Soc. 2, 225–255 (1989). https://doi.org/10.2307/1990977

    Article  MathSciNet  Google Scholar 

  13. Brenier, Y.: Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44, 375–417 (1991). https://doi.org/10.1002/cpa.3160440402

    Article  MathSciNet  Google Scholar 

  14. Brenier, Y.: Generalized solutions and hydrostatic approximation of the Euler equations. Physica D 237, 1982–1988 (2008)

    Article  MathSciNet  Google Scholar 

  15. Carlier, G., Nazaret, B.: Optimal transportation for the determinant. ESAIM Control Optim. Calc. Var. 14, 678–698 (2008). https://doi.org/10.1051/cocv:2008006

    Article  MathSciNet  Google Scholar 

  16. Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., Joulin, A.: Unsupervised learning of visual features by contrasting cluster assignments. In: Advances in Neural Information Processing Systems, vol. 33, pp. 9912–9924 (2020)

  17. Courty, N., Flamary, R., Habrard, A., Rakotomamonjy, A.: Joint distribution optimal transportation for domain adaptation. In: Advances in Neural Information Processing Systems, vol. 30 (2017)

  18. Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems, vol. 26 (2013)

  19. Cuturi, M., Peyré, G.: Semidual regularized optimal transport. SIAM Rev. 60, 941–965 (2018). https://doi.org/10.1137/18M1208654

    Article  MathSciNet  Google Scholar 

  20. De, S., Bartók, A.P., Csányi, G., Ceriotti, M.: Comparing molecules and solids across structural and alchemical space. Phys. Chem. Chem. Phys. 18, 13754–13769 (2016). https://doi.org/10.1039/C6CP00415F

    Article  Google Scholar 

  21. de Acosta, A.: Invariance principles in probability for triangular arrays of \(B\)-valued random vectors and some applications. Ann. Probab. 10, 346–373 (1982)

    Article  MathSciNet  Google Scholar 

  22. Dessein, A., Papadakis, N., Rouas, J.-L.: Regularized optimal transport and the rot mover’s distance. J. Mach. Learn. Res. 19, 590–642 (2018)

    MathSciNet  Google Scholar 

  23. Di Marino, S., Gerolin, A., Nenna, L.: Optimal transportation theory with repulsive costs. In: Topological Optimization and Optimal Transport, vol. 17 of Radon Series on Computational and Applied Mathematics, De Gruyter, Berlin, pp. 204–256 (2017)

  24. Elvander, F., Haasler, I., Jakobsson, A., Karlsson, J.: Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion. Signal Process. 171, 107474 (2020)

    Article  Google Scholar 

  25. Fan, J., Haasler, I., Karlsson, J., Chen, Y.: On the complexity of the optimal transport problem with graph-structured cost. In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR, pp. 9147–9165 (2022). https://proceedings.mlr.press/v151/fan22a.html

  26. Feydy, J., Séjourné, T., Vialard, F.-X., Amari, S., Trouvé, A., Peyré, G.: Interpolating between optimal transport and MMD using Sinkhorn divergences. In: The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, pp. 2681–2690 (2019)

  27. Flamary, R., Courty, N., Gramfort, A., Alaya, M.Z., Boisbunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N., Janati, H., Rakotomamonjy, A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D.J., Tavenard, R., Tong, A., Vayer, T.: POT: python optimal transport. J. Mach. Learn. Res. 22, 1–8 (2021)

    Google Scholar 

  28. Friesecke, G., Schulz, A.S., Vögler, D.: Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems. SIAM J. Sci. Comput. 44, A1632–A1654 (2022). https://doi.org/10.1137/21M140732X

    Article  MathSciNet  Google Scholar 

  29. Frogner, C., Zhang, C., Mobahi, H., Araya, M., Poggio, T.A.: Learning with a Wasserstein loss. In: Advances in Neural Information Processing Systems, vol. 28 (2015). https://proceedings.neurips.cc/paper/2015/file/a9eb812238f753132652ae09963a05e9-Paper.pdf

  30. Gangbo, W.: An introduction to the mass transportation theory and its applications. In: UCLA Lecture Notes (2004). https://www.math.ucla.edu/~wgangbo/publications/notecmu.pdf

  31. Gangbo, W., McCann, R.J.: The geometry of optimal transportation. Acta Math. 177, 113–161 (1996). https://doi.org/10.1007/BF02392620

    Article  MathSciNet  Google Scholar 

  32. Gangbo, W., Świȩch, A.: Optimal maps for the multidimensional Monge–Kantorovich problem. Commun. Pure Appl. Math. 51, 23–45 (1998). https://doi.org/10.1002/(SICI)1097-0312

    Article  MathSciNet  Google Scholar 

  33. Garcia Trillos, N., Jacobs, M., Kim, J.: The multimarginal optimal transport formulation of adversarial multiclass classification, arXiv:2204.12676 (2022)

  34. Genevay, A., Peyré, G., Cuturi, M.: Learning generative models with Sinkhorn divergences. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 1608–1617 (2018)

  35. Haasler, I., Ringh, A., Chen, Y., Karlsson, J.: Multimarginal optimal transport with a tree-structured cost and the Schrödinger bridge problem. SIAM J. Control. Optim. 59, 2428–2453 (2021). https://doi.org/10.1137/20M1320195

    Article  MathSciNet  Google Scholar 

  36. Haasler, I., Singh, R., Zhang, Q., Karlsson, J., Chen, Y.: Multi-marginal optimal transport and probabilistic graphical models. IEEE Trans. Inform. Theory 67, 4647–4668 (2021). https://doi.org/10.1109/tit.2021.3077465

    Article  MathSciNet  Google Scholar 

  37. Jacobs, M., Léger, F.: A fast approach to optimal transport: the back-and-forth method. Numer. Math. 146, 513–544 (2020). https://doi.org/10.1007/s00211-020-01154-8

    Article  MathSciNet  Google Scholar 

  38. Jacobs, M., Léger, F.: The back-and-forth method. https://github.com/Math-Jacobs/bfm (2021)

  39. Kellerer, H.G.: Duality theorems for marginal problems. Z. Wahrsch. Verw. Gebiete 67, 399–432 (1984). https://doi.org/10.1007/BF00532047

    Article  MathSciNet  Google Scholar 

  40. Khoo, Y., Lin, L., Lindsey, M., Ying, L.: Semidefinite relaxation of multimarginal optimal transport for strictly correlated electrons in second quantization. SIAM J. Sci. Comput. 42, B1462–B1489 (2020). https://doi.org/10.1137/20M1310977

    Article  MathSciNet  Google Scholar 

  41. Kitagawa, J., Mérigot, Q., Thibert, B.: Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. (JEMS) 21, 2603–2651 (2019). https://doi.org/10.4171/JEMS/889

    Article  MathSciNet  Google Scholar 

  42. Li, W., Ryu, E.K., Osher, S., Yin, W., Gangbo, W.: A parallel method for earth mover’s distance. J. Sci. Comput. 75, 182–197 (2018). https://doi.org/10.1007/s10915-017-0529-1

    Article  MathSciNet  Google Scholar 

  43. Lin, T., Ho, N., Cuturi, M., Jordan, M.I.: On the complexity of approximating multimarginal optimal transport. J. Mach. Learn. Res. 23, 1–43 (2022)

    MathSciNet  Google Scholar 

  44. Lucet, Y.: Faster than the fast Legendre transform, the linear-time Legendre transform. Numer. Algorithms 16, 171–185 (1997)

    Article  MathSciNet  Google Scholar 

  45. Maddalena, F., Solimini, S., Morel, J.: A variational model of irrigation patterns. Interfaces Free Bound. 5, 391–415 (2003). https://doi.org/10.4171/IFB/85

    Article  MathSciNet  Google Scholar 

  46. Mérigot, Q., Mirebeau, J.: Minimal geodesics along volume-preserving maps, through semidiscrete optimal transport. SIAM J. Numer. Anal. 54, 3465–3492 (2016). https://doi.org/10.1137/15M1017235

    Article  MathSciNet  Google Scholar 

  47. Neufeld, A., Xiang, Q.: Numerical method for feasible and approximately optimal solutions of multi-marginal optimal transport beyond discrete measures, arXiv:2203.01633 (2022)

  48. Papadakis, N., Peyré, G., Oudet, E.: Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7, 212–238 (2014). https://doi.org/10.1137/130920058

    Article  MathSciNet  Google Scholar 

  49. Parno, M., Zhou, B.: MMOT2d. https://github.com/simda-muri/mmot (2022)

  50. Parno, M.D., West, B.A., Song, A.J., Hodgdon, T.S., O’Connor, D.T.: Remote measurement of sea ice dynamics with regularized optimal transport. Geophys. Res. Lett. 46, 5341–5350 (2019). https://doi.org/10.1029/2019GL083037

    Article  Google Scholar 

  51. Pass, B.: Uniqueness and Monge solutions in the multimarginal optimal transportation problem. SIAM J. Math. Anal. 43, 2758–2775 (2011). https://doi.org/10.1137/100804917

    Article  MathSciNet  Google Scholar 

  52. Pass, B.: Multi-marginal optimal transport: theory and applications. ESAIM Math. Model. Numer. Anal. 49, 1771–1790 (2015). https://doi.org/10.1051/m2an/2015020

    Article  MathSciNet  Google Scholar 

  53. Peletier, M., Röger, M.: Partial localization, lipid bilayers, and the elastica functional. Arch. Ration. Mech. Anal. 193, 475–537 (2009). https://doi.org/10.1007/s00205-008-0150-4

    Article  MathSciNet  Google Scholar 

  54. Santambrogio, F.: Optimal Transport for Applied Mathematicians, vol. 87 of Progress in Nonlinear Differential Equations and their Applications, Birkhäuser (2015). https://doi.org/10.1007/978-3-319-20828-2Calculus of variations, PDEs, and modeling

  55. Saumier, L., Khouider, B., Agueh, M.: Optimal transport for particle image velocimetry: real data and postprocessing algorithms. SIAM J. Appl. Math. 75, 2495–2514 (2015). https://doi.org/10.1137/140988814

    Article  MathSciNet  Google Scholar 

  56. Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM J. Sci. Comput. 41, A1443–A1481 (2019). https://doi.org/10.1137/16M1106018

    Article  MathSciNet  Google Scholar 

  57. Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21, 343–348 (1967)

    Article  MathSciNet  Google Scholar 

  58. Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., Guibas, L.: Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans. Graphics (ToG) 34, 1–11 (2015). https://doi.org/10.1145/2766963

    Article  Google Scholar 

  59. Villani, C.: Topics in Optimal Transportation, vol. 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2003). https://doi.org/10.1090/gsm/058

    Book  Google Scholar 

  60. Xia, Q.: Optimal paths related to transport problems. Commun. Contemp. Math. 5, 251–279 (2003). https://doi.org/10.1142/S021919970300094X

    Article  MathSciNet  Google Scholar 

  61. Xia, Q., Zhou, B.: The existence of minimizers for an isoperimetric problem with Wasserstein penalty term in unbounded domains. Adv. Calc. Var. (2021). https://doi.org/10.1515/acv-2020-0083

    Article  Google Scholar 

  62. Yang, Y., Engquist, B., Sun, J., Hamfeldt, B.F.: Application of optimal transport and the quadratic Wasserstein metric to full-waveform inversion. Geophysics 83, R43–R62 (2018). https://doi.org/10.1190/geo2016-0663.1

    Article  Google Scholar 

Download references

Acknowledgements

We would like to thank Anne Gelb, Yoonsang Lee, Doug Cochran, Xianfeng David Gu and James Ronan for many fruitful conversations. We would like thank anonymous referees for their careful reading and valuable suggestions. This work was funded in part by US Office of Naval Research MURI grant N00014-20-1-2595.

Author information

Authors and Affiliations

  1. Department of Mathematics, Dartmouth College, Hanover, NH, USA

    Bohan Zhou & Matthew Parno

Authors
  1. Bohan Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthew Parno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bohan Zhou.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Funding: ONR MURI #N00014-20-1-2595.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 3523 KB)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhou, B., Parno, M. Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs. J Sci Comput 100, 25 (2024). https://doi.org/10.1007/s10915-024-02572-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-024-02572-8

Keywords

Mathematics Subject Classification

Search

Navigation