Abstract

We propose a unifying framework for generalising the Wasserstein-1 metric to a discrepancy measure between nonnegative measures of different mass. This generalization inherits the convexity and computational efficiency from the Wasserstein-1 metric, and it includes several previous approaches from the literature as special cases. For various specific instances of the generalized Wasserstein-1 metric we furthermore demonstrate their usefulness in applications by numerical experiments.

Author information

Contact details are reproduced from the original publication and may be historical.

Bernhard Schmitzer

Institut für Analysis und Numerik, Westfälische Wilhelms-Universität, Einsteinstr. 62, 48149 Münster, Germany

schmitzer@uni-muenster.de

Benedikt Wirth

Institut für Analysis und Numerik, Westfälische Wilhelms-Universität, Einsteinstr. 62, 48149 Münster, Germany

Keywords

  • Convex optimization
  • unbalanced optimal transport
  • minimum-cost flow
  • Kantorovich-Rubinstein formula

Mathematics Subject Classification

49M29, 65K10

References

  1. L. Ambrosio, N. Fusco, D. Pallara: Functions of Bounded Variation and Free Discontinuity Problems, Oxford University Press, Oxford (2000).https://doi.org/10.1093/oso/9780198502456.001.0001Google Scholar
  2. S. Angenent, S. Haker, A. Tannenbaum: Minimizing flows for the Monge-Kantorovich problem, SIAM J. Math. Analysis 35(1) (2003) 61–97.https://doi.org/10.1137/S0036141002410927Google Scholar
  3. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  4. M. Belkin, P. Niyogi: Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comp. 15(6) (2003) 1373–1396.https://doi.org/10.1162/089976603321780317Google Scholar
  5. J.-D. Benamou: Numerical resolution of an “unbalanced” mass transport problem, ESAIM Math. Modelling Numer. Analysis 37(5) (2003) 851–868.https://doi.org/10.1051/m2an:2003058Google Scholar
  6. J.-D. Benamou, Y. Brenier: A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Mathematik 84(3) (2000) 375–393.https://doi.org/10.1007/s002110050002Google Scholar
  7. J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, G. Peyré: Iterative Bregman Projections for Regularized Transportation Problems, SIAM J. Sci. Comput. 37(2) (2015) A1111–A1138.https://doi.org/10.1137/141000439Google Scholar
  8. G. Bouchitté, G. Buttazzo: New lower semicontinuity results for nonconvex functionals defined on measures, Nonlinear Anal. 15(7) (1990) 679–692.https://doi.org/10.1016/0362-546X(90)90007-4Google Scholar
  9. G. Bouchitté, M. Valadier: Integral representation of convex functionals on a space of measures, J. Funct. Anal. 80(2) (1988) 398–420.https://doi.org/10.1016/0022-1236(88)90009-2Google Scholar
  10. G. Bouchitté, M. Valadier: Multifonctions s.c.i. et régularisée s.c.i. essentielle, Ann. Inst. H. Poincaré Anal. Non Linéaire 6(suppl.) (1989) 123–149.https://doi.org/10.1016/s0294-1449(17)30018-5Google Scholar
  11. K. Bredies, T. Pock, B. Wirth: Convex relaxation of a class of vertex penalizing functionals, J. Math. Imaging Vision 47(3) (2013) 278–302.https://doi.org/10.1007/s10851-012-0347-xGoogle Scholar
  12. L. A. Caffarelli, R. J. McCann: Free boundaries in optimal transport and Monge-Ampère obstacle problems, Annals of Math. 171(2) (2010) 673–730.https://doi.org/10.4007/annals.2010.171.673Google Scholar
  13. C. Castaing, M. Valadier: Convex Analysis, Measurable Multifunctions, Lecture Notes in Mathematics 580, Springer, Berlin et al. (1977).https://doi.org/10.1007/BFb0087685Google Scholar
  14. A. Chambolle, T. Pock: A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40(1) (2010) 120–145.https://doi.org/10.1007/s10851-010-0251-1Google Scholar
  15. T. F. Chan, S. Esedoglu: Aspects of total variation regularized L1 function approximation, SIAM J. Appl. Math. 65(5) (2005) 1817–1837.https://doi.org/10.1137/040604297Google Scholar
  16. L. Chizat, G. Peyré, B. Schmitzer, F.-X. Vialard: An interpolating distance between optimal transport and Fisher-Rao metrics, Found. Comp. Math. 18(1) (2018) 1-–44.https://doi.org/10.1007/s10208-016-9331-yGoogle Scholar
  17. L. Chizat, G. Peyré, B. Schmitzer, F.-X. Vialard: Unbalanced optimal transport: Dynamic and Kantorovich formulations, J. Functional Analysis, to appear, arXiv: 1508.05216.Google Scholar
  18. M. Cuturi: Sinkhorn distances: Lightspeed computation of optimal transportation distances, in: Advances in Neural Information Processing Systems 26 (NIPS 2013) (2013) 2292–2300.Google Scholar
  19. J. Dolbeault, B. Nazaret, G. Savaré: A new class of transport distances between measures, Calc. Var. Partial Differential Equations 34(2) (2009) 193–231.https://doi.org/10.1007/s00526-008-0182-5Google Scholar
  20. D. A. Edwards: A simple proof in Monge-Kantorovich duality theory, Studia Mathematica 200(1) (2010) 67–77.https://doi.org/10.4064/sm200-1-4Google Scholar
  21. C. Goffman, J. Serrin: Sublinear functions of measures and variational integrals, Duke Math. J. 31 (1964) 159–178.https://doi.org/10.1215/S0012-7094-64-03115-1Google Scholar
  22. S. Kondratyev, L. Monsaingeon, D. Vorotnikov: A new optimal transport distance on the space of finite Radon measures, Adv. Differential Equations 21(11-12) (2016) 1117–1164.https://doi.org/10.57262/ade/1476369298Google Scholar
  23. J. Lellmann, D. A. Lorenz, C. Schönlieb, T. Valkonen: Imaging with Kantorovich-Rubinstein discrepancy, SIAM J. Imaging Science 7(4) (2014) 2833–2859.https://doi.org/10.1137/140975528Google Scholar
  24. M. Liero, A. Mielke, G. Savaré: Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures, Inventiones Math. 211(3) (2018) 969–1117.https://doi.org/10.1007/s00222-017-0759-8Google Scholar
  25. H. Ling, K. Okada: An efficient earth mover’s distance algorithm for robust histogram comparison, IEEE Trans. Pattern Anal. Mach. Intell. 29(5) (2007) 840–853.https://doi.org/10.1109/TPAMI.2007.1058Google Scholar
  26. D. G. Luenberger: Optimization by Vector Space Methods, John Wiley, New York et al. (1969).Google Scholar
  27. O. Pele, M. Werman: A linear time histogram metric for improved SIFT matching, in: European Conference on Computer Vision (ECCV 2008), (2008) 495–508.https://doi.org/10.1007/978-3-540-88690-7_37Google Scholar
  28. O. Pele, M. Werman: Fast and robust earth mover’s distances, in: International Conference on Computer Vision (ICCV 2009), (2009) 460–467.https://doi.org/10.1109/ICCV.2009.5459199Google Scholar
  29. J. Rabin, S. Ferradans, N. Papadakis: Adaptive color transfer with relaxed optimal transport, in: International Conference on Image Processing (ICIP 2014) 4852–4856.https://doi.org/10.1109/ICIP.2014.7025983Google Scholar
  30. Y. Rubner, C. Tomasi, L. J. Guibas: The earth mover’s distance as a metric for image retrieval, Int. J. Comp. Vision 40(2) (2000) 99–121.https://doi.org/10.1023/A:1026543900054Google Scholar
  31. F. Santambrogio: Optimal Transport for Applied Mathematicians, Progress in Nonlinear Differential Equations and Their Applications 87, Birkhäuser, Boston (2015).https://doi.org/10.1007/978-3-319-20828-2Google Scholar
  32. B. Schmitzer: A sparse multi-scale algorithm for dense optimal transport, J. Math. Imaging Vision 56(2) (2016) 238-–259.https://doi.org/10.1007/s10851-016-0653-9Google Scholar
  33. J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, L. Guibas: Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Trans. Graphics 34(4) (2015) 66:1–66:11.https://doi.org/10.1145/2766963Google Scholar
  34. C. Villani: Optimal Transport: Old and New, Grundlehren der math. Wissenschaften 338, Springer, Berlin et al. (2009).https://doi.org/10.1007/978-3-540-71050-9Google Scholar
  35. W. Wang, D. Slepčev, S. Basu, J. A. Ozolek, G. K. Rohde: A linear optimal transportation framework for quantifying and visualizing variations in sets of images, Int. J. Comp. Vision 101 (2012) 254–269.https://doi.org/10.1007/s11263-012-0566-zGoogle Scholar

Suggested citation

B. Schmitzer, B. Wirth. “A Framework for Wasserstein-1-Type Metrics.” Journal of Convex Analysis 26 (2019), No. 2, 353–396. https://doi.org/10.68381/jca26020

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2019. Rights now held by Banach Press.