“Dynamical optimal transport on discrete surfaces”
Conference:
Type(s):
Title:
- Dynamical optimal transport on discrete surfaces
Session/Category Title: Mapping + transport
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We propose a technique for interpolating between probability distributions on discrete surfaces, based on the theory of optimal transport. Unlike previous attempts that use linear programming, our method is based on a dynamical formulation of quadratic optimal transport proposed for flat domains by Benamou and Brenier [2000], adapted to discrete surfaces. Our structure-preserving construction yields a Riemannian metric on the (finite-dimensional) space of probability distributions on a discrete surface, which translates the so-called Otto calculus to discrete language. From a practical perspective, our technique provides a smooth interpolation between distributions on discrete surfaces with less diffusion than state-of-the-art algorithms involving entropic regularization. Beyond interpolation, we show how our discrete notion of optimal transport extends to other tasks, such as distribution-valued Dirichlet problems and time integration of gradient flows.
References:
1. Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. 2008. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Springer Science & Business Media.Google Scholar
2. Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1 (1998), 61–76.Google ScholarCross Ref
3. Omri Azencot, Orestis Vantzos, and Mirela Ben-Chen. 2016. Advection-based function matching on surfaces. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 55–64.Google Scholar
4. Jean-David Benamou and Yann Brenier. 2000. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84, 3 (2000), 375–393.Google ScholarCross Ref
5. Jean-David Benamou and Guillaume Carlier. 2015. Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. Journal of Optimization Theory and Applications 167, 1 (2015), 1–26. Google ScholarDigital Library
6. Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. 2015. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing 37, 2 (2015), A1111–A1138.Google ScholarDigital Library
7. Jean-David Benamou, Guillaume Carlier, and Maxime Laborde. 2016. An augmented Lagrangian approach to Wasserstein gradient flows and applications. ESAIM: Proceedings and Surveys 54 (2016), 1–17.Google ScholarCross Ref
8. Jean-David Benamou, Guillaume Carlier, and Filippo Santambrogio. 2017. Variational mean field games. In Active Particles, Volume 1. Springer, 141–171.Google Scholar
9. Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. 2011. Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 158. Google ScholarDigital Library
10. Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1 (2011), 1–122. Google ScholarDigital Library
11. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
12. Yann Brenier. 1991. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics 44, 4 (1991), 375–417.Google ScholarCross Ref
13. Susanne Brenner and Ridgway Scott. 2007. The Mathematical Theory of Finite Element Methods. Vol. 15. Springer Science & Business Media.Google Scholar
14. Shui-Nee Chow, Luca Dieci, Wuchen Li, and Haomin Zhou. 2016. Entropy dissipation semi-discretization schemes for Fokker-Planck equations. arXiv:1608.02628 (2016).Google Scholar
15. Sebastian Claici, Edward Chien, and Justin Solomon. 2018. Stochastic Wasserstein barycenters. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (to appear).Google Scholar
16. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, NIPS 2013. 2292–2300. Google ScholarDigital Library
17. Marco Cuturi and Arnaud Doucet. 2014. Fast computation of Wasserstein barycenters. In International Conference on Machine Learning. 685–693. Google ScholarDigital Library
18. Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Transactions on Graphics (TOG) 31, 6 (2012), 171. Google ScholarDigital Library
19. Fernando de Goes, David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1593–1602.Google Scholar
20. Fernando de Goes, Mathieu Desbrun, and Yiying Tong. 2015a. Vector field processing on triangle meshes. In SIGGRAPH Asia 2015 Courses. ACM, 17. Google ScholarDigital Library
21. Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2014. Weighted Triangulations for Geometry Processing. ACM Trans. Graph. 33, 3 (June 2014), 28:1–28:13. Google ScholarDigital Library
22. Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015b. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (2015), 50–1. Google ScholarDigital Library
23. Julie Digne, David Cohen-Steiner, Pierre Alliez, Fernando De Goes, and Mathieu Desbrun. 2014. Feature-preserving surface reconstruction and simplification from defect-laden point sets. Journal of Mathematical Imaging and Vision 48, 2 (2014), 369–382. Google ScholarDigital Library
24. Jack Edmonds and Richard M Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM) 19, 2 (1972), 248–264. Google ScholarDigital Library
25. Matthias Erbar, Martin Rumpf, Bernhard Schmitzer, and Stefan Simon. 2017. Computation of Optimal Transport on Discrete Metric Measure Spaces. arXiv:1707.06859 (2017).Google Scholar
26. Thomas O Gallouët and Quentin Mérigot. 2017. A Lagrangian scheme à la Brenier for the incompressible Euler equations. Foundations of Computational Mathematics (2017), 1–31.Google Scholar
27. Wilfrid Gangbo and Robert J McCann. 1996. The geometry of optimal transportation. Acta Mathematica 177, 2 (1996), 113–161.Google ScholarCross Ref
28. Nicola Gigli and Jan Maas. 2013. Gromov-Hausdorff convergence of discrete transportation metrics. SIAM Journal on Mathematical Analysis 45, 2 (2013), 879–899.Google ScholarCross Ref
29. Peter Gladbach, Eva Kopfer, and Jan Maas. 2018. Scaling limits of discrete optimal transport. arXiv:1809.01092 (2018).Google Scholar
30. Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control, V. Blondel, S. Boyd, and H. Kimura (Eds.). Springer-Verlag Limited, 95–110.Google Scholar
31. Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx.Google Scholar
32. Kevin Guittet. 2003. On the time-continuous mass transport problem and its approximation by augmented Lagrangian techniques. SIAM J. Numer. Anal. 41, 1 (2003), 382–399. Google ScholarDigital Library
33. Behrend Heeren, Martin Rumpf, Max Wardetzky, and Benedikt Wirth. 2012. Time-Discrete Geodesics in the Space of Shells. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1755–1764. Google ScholarDigital Library
34. Romain Hug, Nicolas Papadakis, and Emmanuel Maitre. 2015. On the convergence of augmented Lagrangian method for optimal transport between nonnegative densities. (2015).Google Scholar
35. Richard Jordan, David Kinderlehrer, and Felix Otto. 1998. The variational formulation of the Fokker-Planck equation. SIAM Journal on Mathematical Analysis 29, 1 (1998), 1–17. Google ScholarDigital Library
36. Jürgen Jost. 2008. Riemannian geometry and geometric analysis. Vol. 42005. Springer.Google Scholar
37. Leonid V Kantorovich. 1942. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), Vol. 37. 199–201.Google Scholar
38. Jun Kitagawa, Quentin Mérigot, and Boris Thibert. 2016. Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv preprint arXiv:1603.05579 (2016).Google Scholar
39. Morton Klein. 1967. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science 14, 3 (1967), 205–220. Google ScholarDigital Library
40. Hugo Lavenant. 2017. Harmonic mappings valued in the Wasserstein space. arXiv:1712.07528 (2017).Google Scholar
41. Bruno Lévy. 2015. A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis 49, 6 (2015), 1693–1715.Google ScholarCross Ref
42. Wuchen Li, Ernest K Ryu, Stanley Osher, Wotao Yin, and Wilfrid Gangbo. 2018. A parallel method for earth mover’s distance. Journal of Scientific Computing 75, 1 (2018), 182–197. Google ScholarDigital Library
43. Zhuoran Lu. 2017. Properties of Soft Maps on Riemannian Manifolds. Ph.D. Dissertation. New York University.Google Scholar
44. Jan Maas. 2011. Gradient flows of the entropy for finite Markov chains. Journal of Functional Analysis 261, 8 (2011), 2250–2292.Google ScholarCross Ref
45. Bertrand Maury, Aude Roudneff-Chupin, and Filippo Santambrogio. 2010. A macroscopic crowd motion model of gradient flow type. Mathematical Models and Methods in Applied Sciences 20, 10 (2010), 1787–1821.Google ScholarCross Ref
46. Robert J McCann. 1997. A convexity principle for interacting gases. Advances in Mathematics 128, 1 (1997), 153–179.Google ScholarCross Ref
47. Quentin Mérigot. 2011. A multiscale approach to optimal transport. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1583–1592.Google Scholar
48. Quentin Mérigot, Jocelyn Meyron, and Boris Thibert. 2018. An algorithm for optimal transport between a simplex soup and a point cloud. SIAM Journal on Imaging Sciences 11, 2 (2018), 1363–1389.Google ScholarCross Ref
49. Quentin Mérigot and Jean-Marie Mirebeau. 2016. Minimal geodesics along volume-preserving maps, through semidiscrete optimal transport. SIAM J. Numer. Anal. 54, 6 (2016), 3465–3492.Google ScholarCross Ref
50. MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual.Google Scholar
51. James B Orlin. 1997. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming 78, 2 (1997), 109–129. Google ScholarDigital Library
52. Felix Otto. 2001. The geometry of dissipative evolution equations: the porous medium equation. (2001).Google Scholar
53. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted averages on surfaces. ACM Transactions on Graphics (TOG) 32, 4 (2013), 60. Google ScholarDigital Library
54. Nicolas Papadakis, Gabriel Peyré, and Edouard Oudet. 2014. Optimal transport with proximal splitting. SIAM Journal on Imaging Sciences 7, 1 (2014), 212–238.Google ScholarCross Ref
55. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15–36.Google ScholarCross Ref
56. Konrad Polthier and Markus Schmies. 2006. Straightest geodesics on polyhedral surfaces. ACM.Google Scholar
57. Filippo Santambrogio. 2015. Optimal transport for applied mathematicians. Birkäuser, NY (2015), 99–102.Google Scholar
58. Filippo Santambrogio. 2018. Crowd motion and evolution PDEs under density constraints.Google Scholar
59. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (TOG) 34, 4 (2015), 66. Google ScholarDigital Library
60. Justin Solomon, Leonidas Guibas, and Adrian Butscher. 2013. Dirichlet energy for analysis and synthesis of soft maps. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 197–206. Google ScholarDigital Library
61. Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. 2012. Soft maps between surfaces. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1617–1626. Google ScholarDigital Library
62. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2014. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics (TOG) 33, 4 (2014), 67. Google ScholarDigital Library
63. Nicolas Garcia Trillos. 2017. Gromov-Hausdorff limit of Wasserstein spaces on point clouds. arXiv:1702.03464 (2017).Google Scholar
64. Juan Luis Vázquez. 2007. The Porous Medium Equation: Mathematical Theory. Oxford University Press.Google Scholar
65. Cédric Villani. 2003. Topics in Optimal Transportation. Number 58. American Mathematical Soc.Google Scholar
66. Cédric Villani. 2008. Optimal Transport: Old and New. Vol. 338. Springer Science & Business Media.Google Scholar
