ENTROPICAL OPTIMAL TRANSPORT, SCHRÖDINGER'S SYSTEM AND ALGORITHMS

doi:10.1007/s10473-021-0623-1

摘要/Abstract

摘要： In this exposition paper we present the optimal transport problem of MongeAmpè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..

关键词: entropical optimal transport, Schrödinger system, Sinkhorn's algorithm, gradient descent

Abstract: In this exposition paper we present the optimal transport problem of MongeAmpè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..

Key words: entropical optimal transport, Schrödinger system, Sinkhorn's algorithm, gradient descent

中图分类号:

46N10

Liming WU. ENTROPICAL OPTIMAL TRANSPORT, SCHRÖDINGER'S SYSTEM AND ALGORITHMS[J]. 数学物理学报(英文版), 2021, 41(6): 2183-2197.

Liming WU. ENTROPICAL OPTIMAL TRANSPORT, SCHRÖDINGER'S SYSTEM AND ALGORITHMS[J]. Acta mathematica scientia,Series B, 2021, 41(6): 2183-2197.

参考文献

[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
[2] Beurling A. An automorphism of product measures. Ann Math, 1960, 72:189-200
[3] Birkhoff G. Extensions of Jentzsch's theorem. Transactions of the American Mathematical Society, 1957, 85(1):219-227
[4] Brenier Y. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics, 1991, 44(4):375-417
[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 W₁-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
[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
[12] Cuturi M. Sinkhorn distances:lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 2013, 26:2292-2300
[13] Dantzig G B. Programming of interdependent activities:II mathematical model. Econometrica, 1949, 17(3/4):200-211
[14] Dantzig G B. Application of the simplex method to a transportation problem. Activity Analysis of Production and Allocation, 1951, 13:359-373
[15] Delon J. Midway image equalization. Journal of Mathematical Imaging and Vision, 2004, 21(2):119-134
[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
[17] El Moselhy T A, Marzouk Y M. Bayesian inference with optimal maps. Journal of Computational Physics, 2012, 231(23):7815-7850
[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
[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
[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
[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
[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
[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
[32] Léonard Ch. From the Schrödinger problem to the Monge-Kantorovich problem. Journal of Functional Analysis, 2012, 262(4):1879-1920
[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
[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
[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
[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
[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
[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
[43] Oliver D S. Minimization for conditional simulation:Relationship to optimal transport. Journal of Computational Physics, 2014, 265:1-15
[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
[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
[49] Rüschendorf L. Convergence of the iterative proportional fitting procedure. Annals of Statistics, 1995, 23(4):1160-1174
[50] Samelson H, et al. On the Perron-Frobenius theorem. Michigan Mathematical Journal, 1957, 4(1):57-59
[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
[53] Sinkhorn R. A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Mathematical Statististics, 1964, 35:876-879
[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
[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, Slepčev 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
[58] Wang W, Slepčev 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
[59] Zhu L, Yang Y, Haker S, Tannenbaum A. An image morphing technique based on optimal mass preserving mapping. IEEE Transactions on Image Processing, 2007, 16(6):1481-1495