×

No-collision transportation maps. (English) Zbl 1433.49058

Summary: Transportation maps between probability measures are critical objects in numerous areas of mathematics and applications such as PDE, fluid mechanics, geometry, machine learning, computer science, and economics. Given a pair of source and target measures, one searches for a map that has suitable properties and transports the source measure to the target one. Here, we study maps that possess the no-collision property; that is, particles simultaneously traveling from sources to targets in a unit time with uniform velocities do not collide. These maps are particularly relevant for applications in swarm control problems. We characterize these no-collision maps in terms of half-space preserving property and establish a direct connection between these maps and binary-space-partitioning (BSP) tree structures. Based on this characterization, we provide explicit BSP algorithms, of cost \(O(n \log n)\), to construct no-collision maps. Moreover, interpreting these maps as approximations of optimal transportation maps, we find that they succeed in computing nearly optimal maps for \(q\)-Wasserstein metric \((q=1,2)\). In some cases, our maps yield costs that are just a few percent off from being optimal.

MSC:

49Q15 Geometric measure and integration theory, integral and normal currents in optimization

Software:

POT; GitHub
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Altschuler, J., Bach, F., Rudi, A., Weed, J.: Approximating the quadratic transportation metric in near-linear time. arXiv preprint arXiv:1810.10046 (2018)
[2] Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, pp. 1961-1971. Curran Associates Inc., USA (2017). http://dl.acm.org/citation.cfm?id=3294771.3294958. Accessed Dec 14 2019
[3] Ambrosio, L.; Gigli, N.; Savaré, G., Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich (2008), Basel: Birkhäuser Verlag, Basel · Zbl 1145.35001
[4] Blum, M.; Floyd, Rw; Pratt, V.; Rivest, Rl; Tarjan, Re, Time bounds for selection, J. Comput. Syst. Sci., 7, 4, 448-461 (1973) · Zbl 0278.68033 · doi:10.1016/S0022-0000(73)80033-9
[5] Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, pp. 2292-2300. Curran Associates, Inc. (2013). http://papers.nips.cc/paper/4927-sinkhorn-distances-lightspeed-computation-of-optimal-transport.pdf
[6] Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: Xing, E.P., Jebara, T. (eds.) Proceedings of the 31st International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 32, pp. 685-693. PMLR, Bejing, China (2014). http://proceedings.mlr.press/v32/cuturi14.html. Accessed Dec 14 2019
[7] Dasgupta, S., Freund, Y.: Random projection trees and low dimensional manifolds. Citeseer (2008) · Zbl 1231.68114
[8] Dasgupta, S., Sinha, K.: Randomized partition trees for exact nearest neighbor search. In: Conference on Learning Theory, pp. 317-337 (2013)
[9] Flamary, R., Courty, N.: POT Python optimal transport library (2017). https://github.com/rflamary/POT. Accessed Dec 14 2019
[10] Genevay, A., Cuturi, M., Peyré, G., Bach, F.: Stochastic optimization for large-scale optimal transport. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, pp. 3440-3448. Curran Associates Inc., USA (2016). http://dl.acm.org/citation.cfm?id=3157382.3157482. Accessed Dec 14 2019
[11] Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pp. 373-380. ACM, New York (2004). 10.1145/1007352.1007413 · Zbl 1192.68179
[12] Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Handbook of Discrete and Computational Geometry. Citeseer (2004)
[13] Indyk, P.: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, pp. 39-42. Society for Industrial and Applied Mathematics, Philadelphia (2007). http://dl.acm.org/citation.cfm?id=1283383.1283388. Accessed Dec 14 2019 · Zbl 1302.68290
[14] Indyk, P., Thaper, N.: Fast image retrieval via embeddings. In: Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision, vol. 2, no. 3, p. 5. (2003)
[15] Jacobs, M., Léger, F.: A fast approach to optimal transport: the back-and-forth method. Preprint (2019). ArXiv:1905.12154 [math.OC] · Zbl 1451.65078
[16] Johnson, J.; Douze, M.; Jégou, H., Billion-scale similarity search with GPUs, IEEE Trans. Big Data (2019) · doi:10.1109/TBDATA.2019.2921572
[17] Knothe, H., Contributions to the theory of convex bodies, Mich. Math. J., 4, 39-52 (1957) · Zbl 0077.35803 · doi:10.1307/mmj/1028990175
[18] Li, K., Malik, J.: Fast k-nearest neighbour search via prioritized DCI. In: Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 2081-2090. JMLR.org (2017)
[19] Musser, Dr, Introspective sorting and selection algorithms, Softw. Pract. Exp., 27, 8, 983-993 (1997) · doi:10.1002/(SICI)1097-024X(199708)27:8983::AID-SPE117>3.0.CO;2-#
[20] Peyré, G., Cuturi, M.: Computational Optimal Transport: With Applications to Data Science. Now (2019). https://ieeexplore.ieee.org/document/8641476. Accessed Dec 14 2019 · Zbl 1475.68011
[21] Radha, H.; Vetterli, M.; Leonardi, R., Image compression using binary space partitioning trees, IEEE Trans. Image Process., 5, 12, 1610-1624 (1996) · doi:10.1109/83.544569
[22] Rosenblatt, M., Remarks on a multivariate transformation, Ann. Math. Stat., 23, 470-472 (1952) · Zbl 0047.13104 · doi:10.1214/aoms/1177729394
[23] Schmitzer, B., Stabilized sparse scaling algorithms for entropy regularized transport problems, SIAM J. Sci. Comput., 41, 3, A1443-A1481 (2019) · Zbl 1422.49034 · doi:10.1137/16M1106018
[24] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Berlin: Springer, Berlin · Zbl 1041.90001
[25] Villani, C., Topics in Optimal Transportation. Graduate Studies in Mathematics (2003), Providence: American Mathematical Society, Providence · Zbl 1106.90001
[26] Villani, C., Optimal Transport, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] (2009), Berlin: Springer, Berlin · Zbl 1156.53003
[27] Wu, X., Image coding by adaptive tree-structured segmentation, IEEE Trans. Inf. Theory, 38, 6, 1755-1767 (1992) · Zbl 0775.94082 · doi:10.1109/18.165448
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.