Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Cited by 2,319

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

Computational Optimal Transport with Applications to Data Sciences

Gabriel, Peyré, Marco, Cuturi · 2019 · Foundations and Trends® in Machine Learning

Abstract

Optimal transport (OT) theory can be informally described using the words of the French mathematician Gaspard Monge (1746-1818): A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The goal of the worker is to erect with all that sand a target pile with a prescribed shape (for example, that of a giant sand castle). Naturally, the worker wishes to minimize her total effort, quantified for instance as the total distance or time spent carrying shovelfuls of sand. Mathematicians interested in OT cast that problem as that of comparing two probability distributions—two different piles of sand of the same volume. They consider all of the many possible ways to morph, transport or reshape the first pile into the second, and associate a “global” cost to every such transport, using the “local” consideration of how much it costs to move a grain of sand from one place to another. Mathematicians are interested in the properties of that least costly transport, as well as in its efficient computation. That smallest cost not only defines a distance between distributions, but it also entails a rich geometric structure on the space of probability distributions. That structure is canonical in the sense that it borrows key geometric properties of the underlying “ground” space on which these distributions are defined. For instance, when the underlying space is Euclidean, key concepts such as interpolation, barycenters, convexity or gradients of functions extend naturally to the space of distributions endowed with an OT geometry. OT has been (re)discovered in many settings and under different forms, giving it a rich history. While Monge’s seminal work was motivated by an engineering problem, Tolstoi in the 1920s and Hitchcock, Kantorovich and Koopmans in the 1940s established its significance to logistics and economics. Dantzig solved it numerically in 1949 within the framework of linear programming, giving OT a firm footing in optimization. OT was later revisited by analysts in the 1990s, notably Brenier, while also gaining fame in computer vision under the name of earth mover’s distances. Recent years have witnessed yet another revolution in the spread of OT, thanks to the emergence of approximate solvers that can scale to large problem dimensions. As a consequence, OT is being increasingly used to unlock various problems in imaging sciences (such as color or texture processing), graphics (for shape manipulation) or machine learning (for regression, classification and generative modeling). This paper reviews OT with a bias toward numerical methods, and covers the theoretical properties of OT that can guide the design of new algorithms. We focus in particular on the recent wave of efficient algorithms that have helped OT find relevance in data sciences. We give a prominent place to the many generalizations of OT that have been proposed in but a few years, and connect them with related approaches originating from statistical inference, kernel methods and information theory. All of the figures can be reproduced using code made available in a companion website1 . This website hosts the book project Computational Optimal Transport. You will also find slides and computational resources.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1561/2200000073

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 3 references

Research works printed but not linked: 426

  1. Abadi, 2016, arXiv:1603.04467 · arXiv
  2. Abraham, 2017, “Tomographic reconstruction from a few views: amulti-marginal optimal transportapproach”, Applied Mathematics & Optimization, 75, 55, 10.1007/s00245-015-9323-3 · doi:10.1007/s00245-015-9323-3
  3. Adams, 2011, arXiv preprint arXiv:1106.1925 · arXiv
  4. Agueh, 2013, “One-dimensional numericalalgorithms for gradient flows in the p-Wassersteinspaces”, Acta Applicandae Mathematicae, 125, 121, 10.1007/s10440-012-9783-2 · doi:10.1007/s10440-012-9783-2
  5. Agueh, 2011, “Barycenters in the Wasserstein space”, SIAM Journal on Mathematical Analysis, 43, 904, 10.1137/100805741 · DOI · Paper page
  6. Agueh, 2017, “Vers un théorème dela limite centrale dans l’espace deWasserstein?, Comptes Rendus Mathematique, 355, 812, 10.1016/j.crma.2017.05.010 · doi:10.1016/j.crma.2017.05.010
  7. Ali, 1966, “A general class of coefficients ofdivergence of one distribution fromanother”, Journal of the Royal Statistical Society. Series B (Methodological), 28, 131, 10.1111/j.2517-6161.1966.tb00626.x · DOI · Paper page
  8. Allen-Zhu, 2017, arXiv:1704.02315 · arXiv
  9. Al-Rfou, 2016, CoRR
  10. Altschuler, 2017, “Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration”
  11. #x00C4;lvarez-Esteban, 2016, A fixed-point approach to barycenters in Wasserstein space, Journal of Mathematical Analysis and Applications, 441, 744, 10.1016/j.jmaa.2016.04.045 · DOI
  12. Alvarez-Melis, 2019, Towards Optimal Transport with Global Invariances
  13. Amari, 2018, Information geometry connecting Wasserstein distance and Kullback-Leibler divergence via the entropy-relaxed transportation problem, Information Geometry, 13, 10.1007/s41884-018-0002-8 · DOI
  14. Ambrosio, 2009, Geodesics in the space of measurepreserving maps and plans, Archive for Rational Mechanics and Analysis, 194, 421, 10.1007/s00205-008-0189-2 · doi:10.1007/s00205-008-0189-2
  15. Anderes, 2016, Discrete Wasserstein barycenters: optimal transport for discrete data, Mathematical Methods of Operations Research, 84, 389, 10.1007/s00186-016-0549-x · DOI
  16. Andoni, 2008, Society for Industrial and Applied Mathematics, 343
  17. Andoni, 2018, Snowflake universality of Wasserstein spaces, Annales scientifiques de l’École normale supérieure, 51, 657, 10.24033/asens.2363 · doi:10.24033/asens.2363
  18. Arjovsky, 2017, Wasserstein generative adversarial networks, Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, 70, 214
  19. Aurenhammer, 1987, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, 16, 78, 10.1137/0216006 · DOI · Paper page
  20. Aurenhammer, 1998, Minkowski-type theorems and least-squares clustering, Algorithmica, 20, 61, 10.1007/PL00009187 · DOI · Paper page
  21. Averbuch, 2001, Tech. Rep., Stanford University
  22. Bach, 2010, Self-concordant analysis for logistic regression, Electronic Journal of Statistics, 384
  23. Bach, 2014, Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression, Journal of Machine Learning Research, 15, 595
  24. Bacharach, 1965, Estimating nonnegative matrices from marginal data, International Economic Review, 6, 294, 10.2307/2525582 · doi:10.2307/2525582
  25. Barvinok, 2002, Graduate Studies in Mathematics
  26. Bassetti, 2006, On minimum Kantorovich distance estimators, Statistics & Probability Letters, 76, 1298, 10.1016/j.spl.2006.02.001 · doi:10.1016/j.spl.2006.02.001
  27. Bauschke, 2011, Convex analysis and monotone operator theory in Hilbert spaces, 10.1007/978-1-4419-9467-7 · DOI · Paper page
  28. Bauschke, 2000, Dykstra’s algorithm with Bregman projections: a convergence proof, Optimization, 48, 409, 10.1080/02331930008844513 · doi:10.1080/02331930008844513
  29. Beck, 2003, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, 31, 167, 10.1016/S0167-6377(02)00231-6 · DOI · Paper page
  30. Beckmann, 1952, A continuous model of transportation, Econometrica, 20, 643, 10.2307/1907646 · doi:10.2307/1907646
  31. Beiglbock, Modelindependent bounds for option prices: a mass transport approach, Finance and Stochastics, 17, 477, 10.1007/s00780-013-0205-8 · doi:10.1007/s00780-013-0205-8
  32. Beirlant, 1997, Nonparametric entropy estimation: an overview, International Journal of Mathematical and Statistical Sciences, 6, 17
  33. Benamou, 2003, Numerical resolution of an “unbalanced” mass transport problem, ESAIM: Mathematical Model ling and Numerical Analysis, 37, 851, 10.1051/m2an:2003058 · doi:10.1051/m2an:2003058
  34. Benamou, 2000, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numerische Mathematik, 84, 10.1007/s002110050002 · DOI · Paper page
  35. Benamou, 2015, Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, Journal of Optimization Theory and Applications, 167, 1, 10.1007/s10957-015-0725-9 · doi:10.1007/s10957-015-0725-9
  36. Benamou, 2015, Iterative Bregman projections for regularized transportation problems, SIAM Journal on Scientific Computing, 37, A1111, 10.1137/141000439 · DOI · Paper page
  37. Benamou, 2016, Discretization of functionals involving the Monge-Ampere operator, Numerische Mathematik, 134, 611, 10.1007/s00211-015-0781-y · doi:10.1007/s00211-015-0781-y
  38. Benamou, 2016, Monotone and consistent discretization of the Monge-Ampere operator, Mathematics of Computation, 85, 2743, 10.1090/mcom/3080 · doi:10.1090/mcom/3080
  39. Benamou, 2014, Journal of Computational Physics
  40. Berg, 1984, Graduate Texts in Mathematics, No.100
  41. Berlinet, 2003, Reproducing Kernel Hilbert Spaces in Probability and Statistics
  42. Bernton, 2018, Proceedings of the 31st Conference On Learning Theory, 1777
  43. Bernton, 2017, arXiv preprint arXiv:1701.05146 · arXiv
  44. Bertsekas, 1981, Mathematical Programming, 21, 152, 10.1007/BF01584237 · DOI · Paper page
  45. Bertsekas, 1992, Auction algorithms for network flow problems: a tutorial introduction, Computational Optimization and Applications, 1, 7, 10.1007/BF00247653 · DOI · Paper page
  46. Bertsekas, 1998, Network Optimization: Continuous and Discrete Models Athena Scientific
  47. Bertsekas, 1988, Dual coordinate step methods for linear network flow problems, Mathematical Programming, 42, 203, 10.1007/BF01589405 · doi:10.1007/bf01589405
  48. Bertsimas, 1997, Introduction to Linear Optimization
  49. Bhatia, 2018, Expositiones Mathe- maticae, to appear
  50. Bigot, 2017, arXiv preprint arXiv:1711.08947 · arXiv
  51. Bigot, 2017, Geodesic PCA in the Wasserstein space by convex PCA, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 53, 1, 10.1214/15-AIHP706 · doi:10.1214/15-aihp706
  52. Bigot, 2012, arXiv:1212.2562 · arXiv
  53. Bigot, 2012, “Consistent estimation of a population barycenter in the Wasserstein space”
  54. Birkhoff, 1946, Tres observaciones sobre el algebra lineal, Universidad Nacional de Tucumán Revista Series A, 5, 147
  55. Birkhoff, 1957, Transactions of the American Mathematical Society, 85, 219
  56. Blanchet, 2008, Convergence of the mass-transport steepest descent scheme for the subcritical Patlak- Keller-Segel model, SIAM Journal on Numerical Analysis, 46, 691, 10.1137/070683337 · doi:10.1137/070683337
  57. Blanchet, 2015, Optimal transport and Cournot- Nash equilibria, Mathematics of Operations Research, 41, 125, 10.1287/moor.2015.0719 · DOI
  58. Boissard, 2011, Electronic Journal of Probability, 16: 2296
  59. Boissard, 2015, Distribution’s template estimate with Wasserstein metrics, Bernoul li, 21
  60. Bolley, 2007, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probability Theory and Related Fields, 137, 541, 10.1007/s00440-006-0004-7 · DOI · Paper page
  61. Bonneel, 2016, Wasserstein barycentric coordinates: histogram regression using optimal transport, ACM Transactions on Graphics, 35, 71:1, 10.1145/2897824.2925918 · DOI
  62. Bonneel, 2015, Sliced and Radon Wasserstein barycenters of measures, Journal of Mathematical Imaging and Vision, 51, 22, 10.1007/s10851-014-0506-3 · DOI · Paper page
  63. Bonneel, 2011, Displacement interpolation using Lagrangian mass transport, ACM Transactions on Graphics, 30, No.158, 10.1145/2070781.2024192 · DOI
  64. Borchardt, 1865, De investigando ordine systematis aequationum differentialium vulgarium cujuscunque, Journal für die reine und angewandte Mathematik, 64, 297
  65. Borg, 2005, Modern Multidimensional Scaling: Theory and Applications
  66. Bousquet, 2017, “From optimal transport to generative modeling: the VEGAN cookbook”
  67. Bregman, 1967, “The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming”, USSR Computational Mathematics and Mathematical Physics, 7, 200, 10.1016/0041-5553(67)90040-7 · DOI · Paper page
  68. Brenier, 1987, “Décomposition polaire et réarrangement monotone des champs de vecteurs”, 305, 805
  69. Brenier, 1990, “The least action principle and the related concept of generalized flows for incompressible perfect fluids”, Journal of the AMS, 2, 225
  70. Brenier, 1991, “Polar factorization and monotone rearrangement of vector-valued functions”, Communications on Pure and Applied Mathematics, 44, 375, 10.1002/cpa.3160440402 · DOI · Paper page
  71. Brenier, 1993, “The dual least action problem for an ideal, incompressible fluid”, Archive for Rational Mechanics and Analysis, 122, 323, 10.1007/BF00375139 · doi:10.1007/bf00375139
  72. Brenier, 1999, “Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations”, Communications on Pure and Applied Mathematics, 52, 411, 10.1002/(SICI)1097-0312(199904)52:4<411::AID-CPA1>3.0.CO;2-3 · doi:10.1002/(sici)1097-0312(199904)52:4<411::aid-cpa1>3.0.co;2-3
  73. Brenier, 2008, “Generalized solutions and hydrostatic approximation of the Euler equations”, Physica D. Nonlinear Phenomena, 237, 1982, 10.1016/j.physd.2008.02.026 · doi:10.1016/j.physd.2008.02.026
  74. Bronstein, 2006, “Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching”, Proceedings of the National Academy of Sciences, 103, 1168, 10.1073/pnas.0508601103 · DOI · Paper page
  75. Bronstein, 2010, “A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching”, International Journal on Computer Vision, 89, 266, 10.1007/s11263-009-0301-6 · DOI · Paper page
  76. Brualdi, 2006, Combinatorial Matrix Classes, Vol. 108, 10.1017/CBO9780511721182 · doi:10.1017/cbo9780511721182
  77. Burago, 2001, A Course in Metric Geometry, Vol. 33, 10.1090/gsm/033 · DOI · Paper page
  78. Bures, 1969, “An extension of Kakutani’s theorem on infinite product measures to the tensor product of semifinite w*-algebras”, Transactions of the American Mathematical Society, 135, 199
  79. Burger, 2010, “A mixed finite element method for nonlinear diffusion equations”, Kinetic and Related Models, 3, 59, 10.3934/krm.2010.3.59 · doi:10.3934/krm.2010.3.59
  80. Burger, 2012, “Regularised regression and density estimation based on optimal transport”, 2, 209
  81. Buttazzo, 2012, “Optimaltransport formulation of electronic density-functional theory”, 85, 062
  82. Caffarelli, 2003, “The Monge-Ampere equation and optimal transportation, an elementary review, 1
  83. Caffarelli, 1999, “Problem of reflector design with given far-field scattering data”, Monge Ampère equation: applications to geometry and optimization, Vol. 226
  84. Caffarelli, 2010, #x201C;Free boundaries in optimal transport and Monge-Ampère obstacle problems”, Annals of Mathematics, 171, 673, 10.4007/annals.2010.171.673 · doi:10.4007/annals.2010.171.673
  85. Caffarelli, 2002, “Constructing optimal maps for Monge’s transport problem as a limit of strictly convex costs”, Journal of the American Mathematical Society, 15, 1, 10.1090/S0894-0347-01-00376-9 · doi:10.1090/s0894-0347-01-00376-9
  86. Canas, 2012, Advances in Neural Information Processing Systems 25, 2492
  87. Carlen, 2014, “An analog of the 2-Wasserstein metric in non-commutative probability under which the fermionic Fokker- Planck equation is gradient flow for the entropy”, Communications in Mathematical Physics, 331, 887, 10.1007/s00220-014-2124-8 · doi:10.1007/s00220-014-2124-8
  88. Carlier, 2016, “Vector quantile regression beyond correct specification”
  89. Carlier, 2017, “Convergence of entropic schemes for optimal transport and gradient flows”, 49, 1385
  90. Carlier, 2010, “Matching for teams”, Economic Theory, 42, 397, 10.1007/s00199-008-0415-z · doi:10.1007/s00199-008-0415-z
  91. Carlier, 2010, “From Knothe’s transport to Brenier’s map and a continuation method for optimal transport”, SIAM Journal on Mathematical Analysis, 41, 2554, 10.1137/080740647 · DOI
  92. Carlier, 2008, “Optimal transportation with traffic congestion and Wardrop equilibria”, SIAM Journal on Control and Optimization, 47, 1330, 10.1137/060672832 · doi:10.1137/060672832
  93. Carlier, 2015, “Numerical methods for matching for teams and Wasserstein barycenters”, ESAIM: Mathematical Modelling and Numerical Analysis, 49, 1621, 10.1051/m2an/2015033 · doi:10.1051/m2an/2015033
  94. Carlier, 2019, to appear in ESAIM: COCV
  95. Carrillo, 2015, “A finite-volume method for nonlinear nonlocal equations with a gradient flow structure”, Communications in Computational Physics, 17, 233, 10.4208/cicp.160214.010814a · doi:10.4208/cicp.160214.010814a
  96. Carrillo, 2009, “Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms”, SIAM Journal on Scientific Computing, 31, 4305, 10.1137/080739574 · doi:10.1137/080739574
  97. Censor, 1998, “The Dykstra algorithm with Bregman projections”, Communications in Applied Analysis, 2, 407
  98. Censor, 1992, “Proximal minimization algorithm with-functions”, Journal of Optimization Theory and Applications, 73, 451, 10.1007/BF00940051 · DOI · Paper page
  99. Champion, 2008, “The ^-Wasserstein distance: local solutions and existence of optimal transport maps”, SIAM Journal on Mathematical Analysis, 40, 1, 10.1137/07069938X · doi:10.1137/07069938x
  100. Chan, 1996, “Optimal output-sensitive convex hull algorithms in two and three dimensions”, Discrete & Computational Geometry, 16, 361, 10.1007/BF02712873 · DOI
  101. Chen, 2017, “On the matrix Monge-Kantorovich problem”
  102. Chen, 2016, “On the relation between optimal transport and Schrodinger bridges: A stochastic control viewpoint”, Journal of Optimization Theory and Applications, 169, 671, 10.1007/s10957-015-0803-z · DOI · Paper page
  103. Chen, 2016, “Matrix optimal mass transport: a quantum mechanical approach”
  104. Chizat, 2018, “An interpolating distance between optimal transport and Fisher-Rao metrics”, Foundations of Computational Mathematics, 18, 1, 10.1007/s10208-016-9331-y · DOI · Paper page
  105. Chizat, 2018, “Scaling algorithms for unbalanced transport problems”, Mathematics of Computation, 87, 2563, 10.1090/mcom/3303 · DOI · Paper page
  106. Chizat, 2018, “Unbalanced optimal transport: geometry and Kantorovich formulation”, Journal of Functional Analysis, 274, 3090, 10.1016/j.jfa.2018.03.008 · DOI · Paper page
  107. Chow, 2012, “Fokker-Planck equations for a free energy functional or Markov process on a graph”, Archive for Rational Mechanics and Analysis, 203, 969, 10.1007/s00205-011-0471-6 · DOI
  108. Chow, 2017, “A discrete Schrodinger equation via optimal transport on graphs”
  109. Chow, 2017, “Entropy dissipation of Fokker- Planck equations on graphs
  110. Chowdhury, 2016, “Constructing geodesics on the space of compact metric spaces”
  111. Chui, 2000, “A new algorithm for non-rigid point matching”, Computer Vision and Pattern Recognition, 2000. Proceedings. IEEE Conference on, Vol. 2, 44, 10.1109/CVPR.2000.854733 · DOI · Paper page
  112. Ciszar, 1967, “Information-type measures of difference of probability distributions and indirect observations”, Studia Scientiarum Mathematicarum Hungarica, 2, 299
  113. Cohen, 2017, “Matrix scaling and balancing via box constrained Newton’s method and interior point methods”, 10.1109/FOCS.2017.88 · doi:10.1109/focs.2017.88
  114. Cohen, 1999, “The earth mover’s distance under transformation sets”, Proceedings of the Seventh IEEE International Conference on Computer vision, Vol. 2, 1076, 10.1109/ICCV.1999.790393 · doi:10.1109/iccv.1999.790393
  115. Combettes, 2007, “A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery”, IEEE Journal of Selected Topics in Signal Processing, 1, 564, 10.1109/JSTSP.2007.910264 · DOI · Paper page
  116. Cominetti, 1994, “Asymptotic analysis of the exponential penalty trajectory in linear programming”, Mathematical Programming, 67, 169, 10.1007/BF01582220 · doi:10.1007/bf01582220
  117. Condat, 2015, “Fast projection onto the simplex and the i 1 ball”, 1
  118. Costa, 2015, “Fisher information distance: a geometrical reading”, Discrete Applied Mathematics, 197, 59, 10.1016/j.dam.2014.10.004 · DOI
  119. Cotar, 2013, “Density functional theory and optimal transportation with Coulomb cost”, Communications on Pure and Applied Mathematics, 66, 548, 10.1002/cpa.21437 · doi:10.1002/cpa.21437
  120. Courty, 2017, Advances in Neural Information Processing Systems 30, 3730
  121. Courty, 2016, 2016 IEEE International Geoscience and Remote Sensing Symposium, 3571
  122. Courty, 2017, “Optimal transport for domain adaptation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 39, 1853, 10.1109/TPAMI.2016.2615921 · DOI · Paper page
  123. Crane, 2013, “Geodesics in heat: a new approach to computing distance based on heat flow”, ACM Transaction on Graphics, 32, 152:1, 10.1145/2516971.2516977 · DOI · Paper page
  124. Cuesta, 1989, “Notes on the Wasserstein Metric in Hilbert Spaces”, The Annals of Probability, 17, 1264, 10.1214/aop/1176991269 · doi:10.1214/aop/1176991269
  125. Cuturi, 2012, “Positivity and transportation”
  126. Cuturi, 2013, Advances in Neural Information Processing Systems 26, 2292
  127. Cuturi, 2014, #x201C;Ground metric learning”, Journal of Machine Learning Research, 15, 533
  128. Cuturi, 2014, “Fast computation of Wasserstein barycenters”, Proceedings of ICML, Vol. 32., 685
  129. Cuturi, 2007, Advances in Neural Information Processing Systems 19, 329, 10.7551/mitpress/7503.003.0046 · doi:10.7551/mitpress/7503.003.0046
  130. Cuturi, 2016, “A smoothed dual approach for variational Wasserstein problems”, SIAM Journal on Imaging Sciences, 9, 320, 10.1137/15M1032600 · DOI
  131. Cuturi, 2018, “Semidual Regularized Optimal Transport”, 60, 941
  132. Dalalyan, 2017, “Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent”, Proceedings of the 2017 Conference on Learning Theory. Vol. 65. Proceedings of Machine Learning Research, 678
  133. Dalalyan, 2017, “User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient”
  134. Dantzig, 1949, “Programming of interdependent activities: II mathematical model”, Econometrica, 17, 200, 10.2307/1905523 · DOI · Paper page
  135. Dantzig, 1951, “Application of the simplex method to a transportation problem”, Activity Analysis of Production and Allocation, 13, 359
  136. Dantzig, 1983, Mathematical Programming The State of the Art: Bonn 1982, 78, 10.1007/978-3-642-68874-4_4 · doi:10.1007/978-3-642-68874-4_4
  137. Dantzig, 1991, History of mathematical programming: a col lection of personal reminiscences, 257
  138. Dattorro, 2017, Convex Optimization & Euclidean Distance Geometry
  139. De Goes, 2012, “Blue noise through optimal transport”, ACM Transactions on Graphics, 31, 171, 10.1145/2366145.2366190 · DOI
  140. Delon, 2004, “Midway image equalization”, Journal of Mathematical Imaging and Vision, 21, 119, 10.1023/B:JMIV.0000035178.72139.2d · doi:10.1023/b:jmiv.0000035178.72139.2d
  141. Delon, 2010, “Fast transport optimization for Monge costs on the circle”, SIAM Journal on Applied Mathematics, 70, 2239, 10.1137/090772708 · DOI
  142. Delon, 2012, “Local matching indicators for transport problems with concave costs”, SIAM Journal on Discrete Mathematics, 26, 801, 10.1137/110823304 · doi:10.1137/110823304
  143. Dereich, 2013, “Constructive quantization: Approximation by empirical measures”, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 49., 1183, 10.1214/12-AIHP489 · doi:10.1214/12-aihp489
  144. Deriche, 1993, “Recursively implementating the Gaussian and its derivatives”
  145. Dolbeault, 2009, A new class of transport distances between measures, Calculus of Variations and Partial Differential Equations, 34, 193, 10.1007/s00526-008-0182-5 · DOI
  146. Dolinsky, 2014., “Martingale optimal transport and robust hedging in continuous time”., Probability Theory and Related Fields, 160, 391, 10.1007/s00440-013-0531-y · doi:10.1007/s00440-013-0531-y
  147. Dudley, 1969, “The speed of mean Glivenko-Cantelli convergence”, Annals of Mathematical Statistics, 40, 40, 10.1214/aoms/1177697802 · DOI · Paper page
  148. Dupuy, 2016, Arxiv:1612.09585 · arXiv
  149. Dvurechenskii, 2018., Advances in Neural Information Processing Systems 31, 10783
  150. Dvurechensky, 2018, Proceedings Of The 35Th International Conference On Machine Learning. Ed. By J. Dy And A. Krause. Vol. 80. Proceedings Of Machine Learning Research, 1367
  151. Dykstra, 1983, “An algorithm for restricted least squares regression”., Journal American Statistical Association., 78, 839, 10.1080/01621459.1983.10477029 · DOI · Paper page
  152. Dykstra, 1985, “An iterative procedure for obtaining, I-projections onto the intersection of convex sets”. Annals of Probability, 13, 975
  153. Eckstein, 1992, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators”., Mathematical Programming, 55, 293, 10.1007/BF01581204 · DOI · Paper page
  154. Edwards, 1975, Studies in topology. Elsevier., 121, 10.1016/B978-0-12-663450-1.50017-7 · DOI
  155. El Moselhy, 2012, “Bayesian inference with optimal maps”., Journal of Computational Physics., 231, -, 10.1016/j.jcp.2012.07.022 · DOI · Paper page
  156. Endres, 2003., “A new metric for probability distributions”., IEEE Transactions on Information theory, 49, 1858, 10.1109/TIT.2003.813506 · DOI · Paper page
  157. Erbar, 2010, “The heat equation on manifolds as a gradient flow in the Wasserstein space”., Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 46, 1, 10.1214/08-AIHP306 · doi:10.1214/08-aihp306
  158. Erbar, 2014, “Gradient flow structures for discrete porous medium equations”., Discrete and Continuous Dynamical Systems, 1355, 10.3934/dcds.2014.34.1355 · doi:10.3934/dcds.2014.34.1355
  159. Erlander, 1980, Optimal Spatial Interaction and the Gravity Model, 10.1007/978-3-642-45515-5 · doi:10.1007/978-3-642-45515-5
  160. Erlander, 1990, The Gravity Model in Transportation Analysis: Theory and Extensions
  161. Esfahani, 2018, “Data-driven distributionally robust optimizatio e Wasserstein metric:Performance guarantees and tractable reformulations”., Mathematical Programming., 171, 115, 10.1007/s10107-017-1172-1 · DOI · Paper page
  162. Essid, 2017., arXiv:1704.08200 · arXiv
  163. Evans, 1999, Differential Equations Methods for the Monge-Kantorovich Mass Transfer Problem.
  164. Feldman, 2002., “Monge’s transport problem on a Riemannian manifold”., Transaction AMS., 354, 1667, 10.1090/S0002-9947-01-02930-0 · doi:10.1090/s0002-9947-01-02930-0
  165. Feydy, 2017, #x201C;Optimal transport for diffeomorphic registration”., In: Proceedings of MIC- CAI’17, 291
  166. Feydy, 2019., Proceedings of the 22th International Conference on Artificial Intel ligence and Statistics.
  167. Figalli, 2010., “The optimal partial transport problem”., Archive for Rational Mechanics and Analysis., 195, 533, 10.1007/s00205-008-0212-7 · DOI
  168. Flamary, 2016., Advances in Neural Information Processing Systems, 703
  169. Ford, 1962, Flows in Networks. Princeton University Press.
  170. Forrester, 2016, “Relating the Bures measure to the Cauchy two-matrix model”., Communications in Mathematical Physics., 342, 151, 10.1007/s00220-015-2435-4 · DOI
  171. Fournier, 2015, “On the rate of convergence in Wasserstein distance of the empirical measure”, Probability Theory and Related Fields., 162, 707, 10.1007/s00440-014-0583-7 · DOI
  172. Franklin, 1989, “On the scaling of multidimensional matrices”, Linear Algebra and its Applications., 114, 17
  173. Frisch, 2002, “A reconstruction of the initial conditions of the universe by optimal mass transportation”., Nature, 417, 260, 10.1038/417260a · doi:10.1038/417260a
  174. Froese, 2011, “Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampere equation in dimensions two and higher”, SIAM Journal on Numerical Analysis., 49, 1692, 10.1137/100803092 · doi:10.1137/100803092
  175. Frogner, 2015., Advances in Neural Information Processing Systems, 2053
  176. Gabay, 1976, “A dual algorithm for the solution of nonlinear variational problems via finite element approximation”., Computers & Mathematics with Applications., 2, 17, 10.1016/0898-1221(76)90003-1 · DOI · Paper page
  177. Galichon, 2016, Optimal Transport Methods in Economics, 10.23943/princeton/9780691172767.001.0001 · doi:10.23943/princeton/9780691172767.001.0001
  178. Galichon, 2014, “A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options”., Annals of Applied Probability., 24, 312, 10.1214/13-AAP925 · doi:10.1214/13-aap925
  179. Galichon, 2009, Tech. rep. Preprint SSRN-, 1487307
  180. Gallouet, 2017, “A Lagrangian scheme a la Brenier for the incompressible Euler equations”, Foundations of Computational Mathematics., 18, 1
  181. Gallouet, 2017, “A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flows”., SIAM Journal on Mathematical Analysis., 49, 1100, 10.1137/16M106666X · DOI
  182. Gangbo, 1996, “The geometry of optimal transportation”, Acta Mathematica., 177, 113, 10.1007/BF02392620 · DOI
  183. Gangbo, 1998, “Optimal maps for the multidimensional Monge-Kantorovich problem”., Communications on Pure and Applied Mathematics., 51, 23, 10.1002/(SICI)1097-0312(199801)51:1<23::AID-CPA2>3.0.CO;2-H · doi:10.1002/(sici)1097-0312(199801)51:1<23::aid-cpa2>3.0.co;2-h
  184. GAO, 2018., “Robust Hypothesis Testing Using Wasserstein Uncertainty Sets”. In:, Advances in Neural Information Processing Systems 31., 79137923.
  185. >Gelbrich, 1990, Wasserstein metric between measures on Euclidean and Hilbert spaces”. Mathematische Nachrichten., 147, 185
  186. Genevay, 2019, “Sample complexity of Sinkhorn divergences”. In:, Proceedings of the 22th International Conference on Artificial Intelligence and Statistics
  187. Genevay, 2016, “Stochastic optimization for large-scale optimal transport”., Advances in Neural Information Processing Systems., 3440
  188. Genevay, 2017, “GAN and VAE from an optimal transport point of view”. (arXiv preprint arXiv:1706.01807) · arXiv
  189. Genevay, 2018, “Learning generative models with Sinkhorn divergences”. In:, Proceedings of the 21st International Conference on Artificial Intel ligence and Statistics., 1608
  190. Gentil, 2015, arXiv:1510.08230. · arXiv
  191. George, 1989, “The evolution of the minimum degree ordering algorithm”., SIAM Review., 31, 1, 10.1137/1031001 · DOI
  192. Georgiou, 2015., Journal of Mathematical Physics., 56, 033301., 10.1063/1.4915289 · DOI
  193. Getreuer, 2013, Image Processing On Line. 2013:, 286, 10.5201/ipol.2013.87 · DOI
  194. Gianazza, 2009., “The Wasserstein gradient flow of the Fisher information and the quantum drift-diffusion equation”., Archive for Rational Mechanics and Analysis, 194, 133, 10.1007/s00205-008-0186-5 · doi:10.1007/s00205-008-0186-5
  195. >Gibbs, 2002., “On choosing and bounding probability metrics”., International Statistical Review., 70, 419, 10.1111/j.1751-5823.2002.tb00178.x · DOI · Paper page
  196. Glaunes, 2004, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol. 2.
  197. Glorot, 2011, Proceedings of the 28th International Conference on Machine Learning., 513
  198. Glowinski, 1975, “Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires”., ESAIM: Mathematical Modelling and Numerical Analysis., 9, 41
  199. Goes, 2015, “Power particles: an incompressible fluid solver based on power diagrams”., ACM Transaction Graphics., 34, 50:1
  200. Gold, 1998, “New algorithms for 2D and 3D point matching: pose estimation and correspondence”., Pattern Recognition., 31, 1019, 10.1016/S0031-3203(98)80010-1 · DOI · Paper page

200 of 426 shown

Cited by

Metadata

Authors
Gabriel, P., & Marco, C.
Venue
Foundations and Trends® in Machine Learning
Publisher
Emerald
Published
2019-02-12
Volume
11
Issue
5-6
Pages
355-607
ISSN
  • 1935-8237 (ISSN-L)
  • 1935-8245
OpenAlex
W3039256091
Cited by
2,319
References
3
FWCI
258.33
Type
journal article
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.