×

Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case. (English) Zbl 1457.65014

Summary: We consider the problem of finding an optimal transport plan between an absolutely continuous measure and a finitely supported measure of the same total mass when the transport cost is the unsquared Euclidean distance. We may think of this problem as closest distance allocation of some resource continuously distributed over Euclidean space to a finite number of processing sites with capacity constraints. This article gives a detailed discussion of the problem, including a comparison with the much better studied case of squared Euclidean cost. We present an algorithm for computing the optimal transport plan, which is similar to the approach for the squared Euclidean cost by F. Aurenhammer et al. [Algorithmica 20, No. 1, 61–76 (1998; Zbl 0895.68135)] and Q. Mérigot [“A multiscale approach to optimal transport”, Comput. Graph. Forum 30, No. 5, 1583–1592 (2011; doi:10.1111/j.1467-8659.2011.02032.x)]. We show the necessary results to make the approach work for the Euclidean cost, evaluate its performance on a set of test cases, and give a number of applications. The later include goodness-of-fit partitions, a novel visual tool for assessing whether a finite sample is consistent with a posited probability density.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
49Q22 Optimal transportation
51N20 Euclidean analytic geometry

Citations:

Zbl 0895.68135
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altschuler J, Weed J, Rigollet P (2017) Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In: Proceedings of NIPS 2017, pp 1961-1971
[2] Ambrosio L, Pratelli A (2003) Existence and stability results in the \(L^1\) theory of optimal transportation. In: Optimal transportation and applications (Martina Franca, 2001), Lecture Notes in Math., vol 1813. Springer, Berlin, pp 123-160 · Zbl 1065.49026
[3] Arjovsky M, Chintala S, Bottou L (2017) Wasserstein generative adversarial networks. In: Proceedings of the 34th international conference on machine learning, PMLR, vol. 70. Sydney, Australia (2017)
[4] Armijo L (1966) Minimization of functions having Lipschitz continuous first partial derivatives. Pac J Math 16(1):1-3 · Zbl 0202.46105
[5] Aurenhammer, F.; Hoffmann, F.; Aronov, B., Minkowski-type theorems and least-squares clustering, Algorithmica, 20, 1, 61-76 (1998) · Zbl 0895.68135
[6] Basua, S.; Kolouria, S.; Rohde, GK, Detecting and visualizing cell phenotype differences from microscopy images using transport-based morphometry, PNAS, 111, 9, 3448-3453 (2014)
[7] Beckmann, M., A continuous model of transportation, Econometrica, 20, 643-660 (1952) · Zbl 0048.13001
[8] Benamou, JD; Brenier, Y., A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer Math, 84, 375-393 (2000) · Zbl 0968.76069
[9] Boscoe, FP; Henry, KA; Zdeb, MS, A nationwide comparison of driving distance versus straight-line distance to hospitals, Prof Geogr, 64, 2, 188-196 (2012)
[10] Bourne DP, Schmitzer B, Wirth B (2018) Semi-discrete unbalanced optimal transport and quantization. Preprint. arXiv:1808.01962
[11] CGAL (2015) Computational geometry algorithms library (version 4.6.1). http://www.cgal.org · Zbl 1365.68441
[12] Cooper, L., The transportation-location problem, Oper Res, 20, 1, 94-108 (1972) · Zbl 0237.90036
[13] Courty N, Flamary R, Tuia D, Corpetti T (2016) Optimal transport for data fusion in remote sensing. In: 2016 IEEE international geoscience and remote sensing symposium (IGARSS), pp 3571-3574
[14] Crippa, G.; Jimenez, C.; Pratelli, A., Optimum and equilibrium in a transport problem with queue penalization effect, Adv Calc Var, 2, 3, 207-246 (2009) · Zbl 1166.49040
[15] Croux, C.; Filzmoser, P.; Fritz, H., A comparison of algorithms for the multivariate \(L_1\)-median, Comput Stat, 27, 3, 393-410 (2012) · Zbl 1304.65034
[16] Cuturi, M., Sinkhorn distances: lightspeed computation of optimal transport, Proc NIPS, 2013, 2292-2300 (2013)
[17] De Gournay, F.; Kahn, J.; Lebrat, L., Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure, Numer Math, 141, 2, 429-453 (2019) · Zbl 1475.49055
[18] del Barrio, E.; Loubes, JM, Central limit theorems for empirical transportation cost in general dimension, Ann Probab, 47, 2, 926-951 (2018) · Zbl 1466.60042
[19] Fekete, SP; Mitchell, JSB; Beurer, K., On the continuous Fermat-Weber problem, Oper Res, 53, 1, 61-76 (2005) · Zbl 1165.90553
[20] Flamary, R.; Cuturi, M.; Courty, N.; Rakotomamonjy, A., Wasserstein discriminant analysis, Mach Learn, 107, 12, 1923-1945 (2018) · Zbl 1480.62125
[21] Geiß, D.; Klein, R.; Penninger, R.; Rote, G., Optimally solving a transportation problem using Voronoi diagrams, Comput Geom, 46, 8, 1009-1016 (2013) · Zbl 1282.49039
[22] Genevay, A.; Cuturi, M.; Peyré, G.; Bach, F., Stochastic optimization for large-scale optimal transport, Proc NIPS, 2016, 3432-3440 (2016)
[23] Genevay A, Peyré G, Cuturi M (2018) Learning generative models with Sinkhorn divergences. In: Proceedings of the 21st international conference on artificial intelligence and statistics, PMLR, vol 84. Lanzarote, Spain
[24] Gramfort A, Peyré G, Cuturi M (2015) Fast optimal transport averaging of neuroimaging data. In: 24th International conference on information processing in medical imaging (IPMI 2015), lecture notes in computer science, vol 9123, pp 123-160
[25] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J Numer Anal, 23, 4, 707-716 (1986) · Zbl 0616.65067
[26] Guo J, Pan Z, Lei B, Ding C (2017) Automatic color correction for multisource remote sensing images with Wasserstein CNN. Rem Sens 9(5):1-16 (electronic)
[27] Hartmann V (2016) A geometry-based approach for solving the transportation problem with Euclidean cost. Bachelor’s thesis, Institute of Mathematical Stochastics, University of Göttingen. arXiv:1706.07403
[28] Kantorovich L (1942) On the translocation of masses. C R (Doklady) Acad Sci URSS (NS) 37, 199-201 · Zbl 0061.09705
[29] Karavelas MI, Yvinec M (2002) Dynamic additively weighted Voronoi diagrams in 2D. In: Algorithms—ESA 2002. Springer, Berlin, pp 586-598 · Zbl 1019.68608
[30] Kitagawa, J.; Mérigot, Q.; Thibert, B., Convergence of a Newton algorithm for semi-discrete optimal transport, J Eur Math Soc, 21, 2603-2651 (2019) · Zbl 1439.49053
[31] Klatt M, Tameling C, Munk A (2019) Empirical regularized optimal transport: statistical theory and applications. Preprint. arXiv:1810.09880
[32] Luenberger DG, Ye Y (2008) Linear and nonlinear programming, third edn. International series in operations research and management science, 116. Springer, New York · Zbl 1207.90003
[33] Mallozzi, L.; Puerto, J.; Rodríguez-Madrena, M., On location-allocation problems for dimensional facilities, J Optim Theory Appl, 182, 2, 730-767 (2019) · Zbl 1418.90143
[34] McCann, RJ, Existence and uniqueness of monotone measure-preserving maps, Duke Math J, 80, 2, 309-323 (1995) · Zbl 0873.28009
[35] Mérigot, Q., A multiscale approach to optimal transport, Comput Graph. Forum, 30, 5, 1583-1592 (2011)
[36] Monge G (1781) Mémoire sur la théorie des déblais et des remblais. In: Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pp 666-704
[37] Nicolas P (2016) Optimal transport for image processing. Habilitation thesis, Signal and Image Processing, Université de Bordeaux. https://hal.archives-ouvertes.fr/tel-01246096v6
[38] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math Comput, 35, 151, 773-782 (1980) · Zbl 0464.65037
[39] Nocedal, J.; Wright, S., Numerical optimization, Springer Sci, 35, 67-68, 7 (1999) · Zbl 0930.65067
[40] Núñez, M.; Scarsini, M., Competing over a finite number of locations, Econ Theory Bull, 4, 2, 125-136 (2016)
[41] Okazaki N, Nocedal J (2010) libLBFGS (Version 1.10). http://www.chokkan.org/software/liblbfgs/
[42] Peyré G, Cuturi M (2018) Computational optimal transport. now Publishers. arXiv:1803.00567 · Zbl 1475.68011
[43] Pratelli, A., On the equality between Monge’s infimum and Kantorovich’s minimum in optimal mass transportation, Ann Inst H Poincaré Probab Stat, 43, 1, 1-13 (2007) · Zbl 1121.49036
[44] R Core Team (2017) R: a Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. Version 3.3.0. https://www.R-project.org/
[45] Rippl, T.; Munk, A.; Sturm, A., Limit laws of the empirical Wasserstein distance: Gaussian distributions, J Multivar Anal, 151, 90-109 (2016) · Zbl 1351.62064
[46] Santambrogio F (2015) Optimal transport for applied mathematicians, Progress in nonlinear differential equations and their applications, vol 87. Birkhäuser/Springer, Cham · Zbl 1401.49002
[47] Schmitz, MA; Heitz, M.; Bonneel, N.; Ngolè, F.; Coeurjolly, D.; Cuturi, M.; Peyré, G.; Starck, JL, Wasserstein dictionary learning: optimal transport-based unsupervised nonlinear dictionary learning, SIAM J Imaging Sci, 11, 1, 643-678 (2018) · Zbl 1437.94027
[48] Schmitzer, B., A sparse multiscale algorithm for dense optimal transport, J Math Imaging Vis, 56, 2, 238-259 (2016) · Zbl 1351.49037
[49] Schmitzer, B., Stabilized sparse scaling algorithms for entropy regularized transport problems, SIAM J Sci Comput, 41, 3, A1443-A1481 (2019) · Zbl 1422.49034
[50] Schmitzer, B.; Wirth, B., A framework for Wasserstein-1-type metrics, J Convex Anal, 26, 2, 353-396 (2019) · Zbl 1426.49032
[51] Schrieber J, Schuhmacher D, Gottschlich C (2017) DOTmark: a benchmark for discrete optimal transport. IEEE Access, 5
[52] Schuhmacher D, Bähre B, Gottschlich C, Hartmann V, Heinemann F, Schmitzer B, Schrieber J (2019) Transport: computation of optimal transport plans and Wasserstein distances. R package version 0.11-1. https://cran.r-project.org/package=transport
[53] Sherali, HD; Nordai, FL, NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands, Math Oper Res, 13, 1, 32-49 (1988) · Zbl 0651.90025
[54] Solomon J, de Goes F, Peyré G, Cuturi M, Butscher A, Nguyen A, Du T, Guibas L (2015) Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans Graph 34(4): 66:1-66:11 · Zbl 1334.68267
[55] Solomon J, Rustamov R, Guibas L, Butscher A (2014) Earth mover’s distances on discrete surfaces. ACM Trans Graph 33(4): 67:1-67:12 · Zbl 1396.65063
[56] Sommerfeld, M.; Munk, A., Inference for empirical Wasserstein distances on finite spaces, J R Stat Soc: Ser B (Statistical Methodology), 80, 1, 219-238 (2018) · Zbl 1380.62121
[57] Villani C (2009) Optimal transport, old and new, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol 338. Springer, Berlin · Zbl 1156.53003
[58] Wolansky G (2015) Semi-discrete approximation of optimal mass transport. Preprint. arXiv:1502.04309v1 · Zbl 1317.49055
[59] Wolfe, P., Convergence conditions for ascent methods, SIAM Rev, 11, 226-235 (1969) · Zbl 0177.20603
[60] Wolfe, P., Convergence conditions for ascent methods. II. Some corrections, SIAM Rev, 13, 185-188 (1971) · Zbl 0216.26901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.