×

Fast entropic regularized optimal transport using semidiscrete cost approximation. (English) Zbl 1401.65020

Summary: The optimal transportation theory was successfully applied to different tasks on geometric domains as images and triangle meshes. In these applications the transport problem is defined on a Riemannian manifold with geodesic distance \(d(x,y)\). Usually, the cost function used is the geodesic distance \(d\) or the squared geodesic distance \(d^2\). These choices result in the 1-Wasserstein distance, also known as the earth mover’s distance (EMD), or the 2-Wasserstein distance. The entropy regularized optimal transport problem can be solved using the Bregman projection algorithm. This algorithm can be implemented using only matrix multiplications of matrix \(\exp(-C/\varepsilon)\) (pointwise exponent) and pointwise vector multiplications, where \(C\) is a cost matrix, and \(\varepsilon\) is the regularization parameter. In this paper, we obtain a low-rank decomposition of this matrix and exploit it to accelerate the Bregman projection algorithm. Our low-rank decomposition is based on the semidiscrete approximation of the cost function, which is valid for a large family of cost functions, including \(d^p (x, y)\), where \(p \geq 1\). Our method requires the calculation of only a small portion of the distances.

MSC:

65D05 Numerical interpolation
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
49M25 Discrete approximations in optimal control

Software:

advanpix
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Advanpix LLC, Multiprecision Computing Toolbox for MATLAB, version 4.4.7.12739, Tokyo, Japan, 2017, .
[2] M. Agueh and G. Carlier, Barycenters in the Wasserstein space, SIAM J. Math. Anal., 43 (2011), pp. 904–924, . · Zbl 1223.49045
[3] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré, Iterative Bregman projections for regularized transportation problems, SIAM J. Sci. Comput., 37 (2015), pp. A1111–A1138, . · Zbl 1319.49073
[4] J.-D. Benamou, B. D. Froese, and A. M. Oberman, Numerical solution of the optimal transportation problem using the Monge-Ampère equation, J. Comput. Phys., 260 (2014), pp. 107–126. · Zbl 1349.65554
[5] J.-D. Benamou, Y, Brenier, and K. Guittet, The Monge–Kantorovich mass transfer and its computational fluid mechanics formulation, Internat. J. Numer. Methods Fluids, 40 (2002), pp. 21–30. · Zbl 1058.76586
[6] L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7 (1967), pp. 620–631 (in Russian). · Zbl 0186.23807
[7] A. M. Bronstein, M. M. Bronstein, and R. Kimmel, Numerical Geometry of Non-Rigid Shapes, Springer, New York, 2008. · Zbl 1178.68608
[8] M. Chen and M. Chiang, Distributed optimization in networking: Recent advances in combinatorial and robust formulations, in Modeling and Optimization: Theory and Applications, Springer, New York, 2012, pp. 25–52. · Zbl 1327.90037
[9] K. Crane, C. Weischedel, and M. Wardetzky, Geodesics in heat: A new approach to computing distance based on heat flow, ACM Trans. Graphics, 32 (2013), 152.
[10] M. Cuturi and A. Doucet, Fast computation of Wasserstein barycenters, Proc. Mach. Learn. Res., 32 (2014), pp. 685–693.
[11] M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, in Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 2, Lake Tahoe, NV, 2013, pp. 2292–2300.
[12] E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math., 1 (1959), pp. 269–271. · Zbl 0092.16002
[13] P. Drineas and M. W. Mahoney, On the Nystrom method for approximating a Gram matrix for improved kernel-based learning, J. Mach. Learn. Res., 6 (2005), pp. 2153–2175. · Zbl 1222.68186
[14] S. Haker, L. Zhu, A. Tannenbaum, and S. Angenent, Optimal mass transport for registration and warping, Internat. J. Comput. Vis., 60 (2004), pp. 225–240.
[15] D. S. Hochbaum and D. B. Shmoys, A best possible heuristic for the k-center problem, Math. Oper. Res., 10 (1985), pp. 180–184. · Zbl 0565.90015
[16] L. V. Kantorovich, On the translocation of masses, C. R. (Doklady) Acad. Sci. Nauk URSS (N.S.), 37 (1942), pp. 199–201. · Zbl 0061.09705
[17] Y. H. Kim and B. Pass, Multi-marginal optimal transport on Riemannian manifolds, Amer. J. Math., 137 (2015), pp. 1045–1060. · Zbl 1328.49044
[18] R. Kimmel and J. A. Sethian, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci. USA, 95 (1998), pp. 8431–8435. · Zbl 0908.65049
[19] C. Leonard, From the Schrödinger problem to the Monge-Kantorovich problem, J. Funct. Anal., 262 (2012), pp. 1879–1920. · Zbl 1236.49088
[20] B. Lévy, A numerical algorithm for \(L_2\) semi-discrete optimal transport in \(3\)D, ESAIM Math. Model. Numer. Anal., 49 (2015), pp. 1693–1715.
[21] W. Li, P. Yin, and S. Osher, Computations of optimal transport distance with Fisher information regularization, J. Sci. Comput., 75 (2018), pp. 1581–1595. · Zbl 1415.49030
[22] W. Li, E. K. Ryu, S. Osher, W. Yin, and W. Gangbo, A parallel method for earth mover’s distance, J. Sci. Comput., 75 (2018), pp. 182–197. · Zbl 1398.65124
[23] Q. Merigot, A multiscale approach to optimal transport, Comput. Graphics Forum, 30 (2011), pp. 1583–1592.
[24] MOSEK ApS, MOSEK version 8, 2017, .
[25] E. K. Ryu, W. Li, P. Yin, and S. Osher, Unbalanced and partial \(L_1\) Monge-Kantorovich problem: A scalable parallel first-order method, J. Sci. Comput., 75 (2018), pp. 1596–1613. · Zbl 1415.49032
[26] G. Shamai, Y. Aflalo, M. Zibulevsky, and R. Kimmel, Classical scaling revisited, in Proceedings of the IEEE International Conference on Computer Vision (ICCV), IEEE, Washington, DC, 2015.
[27] G. Shamai, M. Zibulevsky, and R. Kimmel, Accelerating the computation of canonical forms for \(3\)D nonrigid objects using multidimensional scaling, in Proceedings of the 2015 Eurographics Workshop on 3D Object Retrieval, Eurographics Association, Aire-la-Ville, Switzerland, 2015.
[28] R. Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums, Amer. Math. Monthly, 74 (1967), pp. 402–405. · Zbl 0166.03702
[29] J. Solomon, F. De Goes, G. Peyre, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas, Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Trans. Graphics, 34 (2015), 66. · Zbl 1334.68267
[30] C. Villani, Topics in Optimal Transportation, Grad. Stud. Math. 58, AMS, Providence, RI, 2003. · Zbl 1106.90001
[31] C. Villani, Optimal Transport: Old and New, Springer, New York, 2009. · Zbl 1156.53003
[32] G. Wolansky, On semi-discrete Monge-Kantorovich and generalized partitions, J. Optim. Theory Appl., 165 (2015), pp. 359–384. · Zbl 1317.49055
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.