SpringerLink
Log in

Entropical Optimal Transport, Schrödinger’s System and Algorithms

  • Published:
Acta Mathematica Scientia Aims and scope Submit manuscript

Abstract

In this exposition paper we present the optimal transport problem of Monge-Ampère-Kantorovitch (MAK in short) and its approximative entropical regularization. Contrary to the MAK optimal transport problem, the solution of the entropical optimal transport problem is always unique, and is characterized by the Schrödinger system. The relationship between the Schrödinger system, the associated Bernstein process and the optimal transport was developed by Léonard [32, 33] (and by Mikami [39] earlier via an h-process). We present Sinkhorn’s algorithm for solving the Schrödinger system and the recent results on its convergence rate. We study the gradient descent algorithm based on the dual optimal question and prove its exponential convergence, whose rate might be independent of the regularization constant. This exposition is motivated by recent applications of optimal transport to different domains such as machine learning, image processing, econometrics, astrophysics etc..

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
EUR 32.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 (Canada)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Altschuler J, Weed J, Rigollet Ph. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in Neural Information Processing Systems, 2017, 30: 1964–1974

    Google Scholar 

  2. Beurling A. An automorphism of product measures. Ann Math, 1960, 72: 189–200

    Article  MathSciNet  Google Scholar 

  3. Birkhoff G. Extensions of Jentzsch’s theorem. Transactions of the American Mathematical Society, 1957, 85(1): 219–227

    MathSciNet  MATH  Google Scholar 

  4. Brenier Y. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics, 1991, 44(4): 375–417

    Article  MathSciNet  Google Scholar 

  5. Brualdi R A. Combinatorial Matrix Classes. Volume 108. Cambridge University Press, 2006

  6. Caffarelli L. The Monge-Ampère equation and optimal transportation, an elementary review//Lecture Notes in Mathematics, Springer-Verlag, 2003: 1–10

  7. Cheng L Y, Li R N, Wu L. Ricci curvature and W1-exponential convergence of Markov processes on graphs. Preprint 2015, in the Ph.D theses of Cheng and Li at AMSS, Chinese Academy of Sciences 2017

  8. Chung F R K. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, 92. Providence, RI: American Mathematical Society, 1997

    MATH  Google Scholar 

  9. Courty N, Flamary R, Tuia D, Corpetti T. Optimal transport for data fusion in remote sensing//IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2016: 3571–3574

  10. Cruzeiro A B, Wu L, Zambrini J C. Bernstein processes associated with a Markov process//Rebolledo R, ed. Stochastic Analysis and Mathematical Physics. ANESTOC’98, Proceedings of the Third International Workshop (Boston) Trends in Mathematics. Birkhäuser, 2000: 41–71

  11. Csiszar I. I-divergence geometry of probability distributions and minimization problems. Annals of Probability, 1975, 3(1): 146–158

    Article  MathSciNet  Google Scholar 

  12. Cuturi M. Sinkhorn distances: lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 2013, 26: 2292–2300

    Google Scholar 

  13. Dantzig G B. Programming of interdependent activities: II mathematical model. Econometrica, 1949, 17(3/4): 200–211

    Article  MathSciNet  Google Scholar 

  14. Dantzig G B. Application of the simplex method to a transportation problem. Activity Analysis of Production and Allocation, 1951, 13: 359–373

    MathSciNet  Google Scholar 

  15. Delon J. Midway image equalization. Journal of Mathematical Imaging and Vision, 2004, 21(2): 119–134

    Article  MathSciNet  Google Scholar 

  16. Di Marino S, Gerolin A. An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm. Journal of Scientific Computing, 2020, 85(2): 27

    Article  Google Scholar 

  17. El Moselhy T A, Marzouk Y M. Bayesian inference with optimal maps. Journal of Computational Physics, 2012, 231(23): 7815–7850

    Article  MathSciNet  Google Scholar 

  18. Erlander S. Optimal Spatial Interaction and the Gravity Model. Volume 173. Springer-Verlag, 1980

  19. Erlander S, Stewart N F. The Gravity Model in Transportation Analysis: Theory and Extensions. 1990

  20. Franklin J, Lorenz J. On the scaling of multidimensional matrices. Linear Algebra and its Applications, 1989, 114: 717–735

    Article  MathSciNet  Google Scholar 

  21. Frisch U, Matarrese S, Mohayaee R, Sobolevski A. A reconstruction of the initial conditions of the universe by optimal mass transportation. Nature, 2002, 417(6886): 260–262

    Article  Google Scholar 

  22. Galichon A, Salanié B. Matching with trade-offs: revealed preferences over competing characteristics. CEPR Discussion Paper No DP7858, 2010

  23. Galichon A. Optimal Transport Methods in Economics. Princeton University Press, 2016

  24. Genevay A, Cuturi M, Peyré G, Bach F. Stochastic optimization for large-scale optimal transport. Advances in Neural Information Processing Systems, 2016: 3440–3448

  25. Graham C, Talay D. Stochastic Simulation and Monte Carlo Methods: Mathematical Foundations of Stochastic Simulation. Stochastic Medelling and Applied Probability 68. Springer, 2013

  26. Gutierrez J, Rabin J, Galerne B, Hurtut T. Optimal patch assignment for statistically constrained texture synthesis//International Conference on Scale Space and Variational Methods in Computer Vision. Springer, 2017: 172–183

  27. Kantorovich L. On the transfer of masses (in russian). Doklady Akademii Nauk, 1942, 37(2): 227–229

    Google Scholar 

  28. Kim S, Ma R, Mesa D, Coleman T P. Efficient Bayesian inference methods via convex optimization and optimal transport//IEEE International Symposium on Information Theory. IEEE, 2013: 2259–2263

  29. Kolouri S, Park S R, Thorpe M, Slepcev D, Rohde G K. Optimal mass transport: signal processing and machine-learning applications. IEEE Signal Processing Magazine, 2017, 34(4): 43–59

    Article  Google Scholar 

  30. Kosowsky J J, Yuille A L. The invisible hand algorithm: Solving the assignment problem with statistical physics. Neural Networks, 1994, 7(3): 477–490

    Article  Google Scholar 

  31. Lai R, Zhao H. Multiscale nonrigid point cloud registration using rotation invariant sliced-wasserstein distance via laplace-beltrami eigenmap. SIAM Journal on Imaging Sciences, 2017, 10(2): 449–483

    Article  MathSciNet  Google Scholar 

  32. Léonard Ch. From the Schrödinger problem to the Monge-Kantorovich problem. Journal of Functional Analysis, 2012, 262(4): 1879–1920

    Article  MathSciNet  Google Scholar 

  33. Léonard Ch. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Continuous Dynamical Systems Series A, 2014, 34(4): 1533–1574

    Article  MathSciNet  Google Scholar 

  34. Li P, Wang Q, Zhang L. A novel earth mover’s distance methodology for image matching with Gaussian mixture models//Proceedings of the IEEE International Conference on Computer Vision. IEEE, 2013: 1689–1696

  35. Liu W, Ma Y T, Wu L. Spectral gap, isoperimetry and concentration on trees. Sci China Math, 2016, 59(3): 539–556

    Article  MathSciNet  Google Scholar 

  36. Ma Y T, Wang R, Wu L. Logarithmic Sobolev, isoperimetry and transport inequalities on graph. Acta Mathematica Sinica, English Series, 2016, 32(10): 1221–1236

    Article  MathSciNet  Google Scholar 

  37. Makihara Y, Yagi Y. Earth mover’s morphing: Topology-free shape morphing using cluster-based EMD flows//Asian Conference on Computer Vision. Springer, 2010: 202–215

  38. Mathon B, Cayre F, Bas P, Macq B. Optimal transport for secure spread-spectrum watermarking of still images. IEEE Transactions on Image Processing, 2014, 23(4): 1694–1705

    Article  MathSciNet  Google Scholar 

  39. Mikami T. Monge’s problem with a quadratic cost by the zero-noise limit of h-path processes. Probab Theory Related Fields, 2004, 129(2): 245–260

    Article  MathSciNet  Google Scholar 

  40. Mikami T. Stochastic Optimal Transportation: Stochastic Control with Fixed Marginals. Springer, 2021

  41. Monge G. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences, 1781: 666–704

  42. Museyko O, Stiglmayr M, Klamroth K, Leugering G. On the application of the Monge-Kantorovich problem to image registration. SIAM Journal on Imaging Sciences, 2009, 2(4): 1068–1097

    Article  MathSciNet  Google Scholar 

  43. Oliver D S. Minimization for conditional simulation: Relationship to optimal transport. Journal of Computational Physics, 2014, 265: 1–15

    Article  MathSciNet  Google Scholar 

  44. Peyré G, Cuturi M. Computational Optimal Transport: With Application in Data Science. Now Foundation and Trends, 2019

  45. Peyré G, Cuturi M. Computational optimal transport. Foundations and Trends in Machine Learning, 2019, 11(5/6): 355–607

    Article  Google Scholar 

  46. Rachev S T, Rüschendorf L. Mass Transportation Problems: Volume I: Theory. Springer Science & Business Media, 1998

  47. Rachev S T, Rüschendorf L. Mass Transportation Problems: Volume II: Applications. Springer Science & Business Media, 1998

  48. Reich S. A nonparametric ensemble transform method for Bayesian inference. SIAM Journal on Scientific Computing, 2013, 35(4): A2013–A2024

    Article  MathSciNet  Google Scholar 

  49. Rüschendorf L. Convergence of the iterative proportional fitting procedure. Annals of Statistics, 1995, 23(4): 1160–1174

    Article  MathSciNet  Google Scholar 

  50. Samelson H, et al. On the Perron-Frobenius theorem. Michigan Mathematical Journal, 1957, 4(1): 57–59

    Article  MathSciNet  Google Scholar 

  51. Santambrogio F. Optimal Transport for Applied Mathematicians. Birkhauser, 2015

  52. Schrödinger E. Über die Umkehrung der Naturgesetze. Sitzungsberichte Preuss Akad Wiss Berlin Phys Math, 1931, 144: 144–153

    MATH  Google Scholar 

  53. Sinkhorn R. A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Mathematical Statististics, 1964, 35: 876–879

    Article  MathSciNet  Google Scholar 

  54. Su Z, Wang Y, Shi R, Zeng W, Sun J, Luo F, Gu X. Optimal mass transport for shape matching and comparison. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(11): 2246–2259

    Article  Google Scholar 

  55. Villani C. Topics in Optimal Transportation. Graduate Studies in Mathematics Series. American Mathematical Society, 2003

  56. Villani C. Optimal Transport: Old and New, 338. Springer Verlag, 2009

  57. Wang W, Ozolek J A, Slepcev D, Lee A B, Chen C, Rohde G K. An optimal transportation approach for nuclear structure-based pathology. IEEE Transactions on Medical Imaging, 2011, 30(3): 621–631

    Article  Google Scholar 

  58. Wang W, Slepcev D, Basu S, Ozolek J A, Rohde G K. A linear optimal transportation framework for quantifying and visualizing variations in sets of images. International Journal of Computer Vision, 2013, 101(2): 254–269

    Article  MathSciNet  Google Scholar 

  59. Zhu L, Yang Y, Haker S, Tannenbaum A. An image morphing technique based on optimal mass preserving map**. IEEE Transactions on Image Processing, 2007, 16(6): 1481–1495

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

I am grateful to Christian Léonard for conversations on this fascinating subject, to Wei Liu and Yuling Jiao of Wuhan University for the communication of several references, to **angdong Li for the kind invitation to the conference on optimal transport held on May 2021 at AMSS, Chinese Academy of Sciences, where the material of this exposition paper was reported.

Author information

Authors and Affiliations

  1. Institute for Advanced Study in Mathematics, Harbin’s Institute of Technology, Harbin, 150001, China

    Liming Wu

  2. Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont-Auvergne (UCA), 63000, Clermont-Ferrand, France

    Liming Wu

Authors
  1. Liming Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liming Wu.

Additional information

Dedicated to the memory of Professor Jiarong YU

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wu, L. Entropical Optimal Transport, Schrödinger’s System and Algorithms. Acta Math Sci 41, 2183–2197 (2021). https://doi.org/10.1007/s10473-021-0623-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10473-021-0623-1

Key words

2010 MR Subject Classification

Search

Navigation