[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

This paper aims at determining under which conditions the semi-discrete optimal transport is twice differentiable with respect to the parameters of the discrete measure and exhibits numerical applications. The discussion focuses on minimal conditions on the background measure to ensure differentiability. We provide numerical illustrations in stippling and blue noise problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Asami, Y.: A note on the derivation of the first and second derivative of objective functions in geographical optimization problems. J. Fac. Eng. Univ. Tokyo (B) 41(1), 1–13 (1991)

    MathSciNet  Google Scholar 

  2. Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  3. Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)

    MATH  Google Scholar 

  5. Brezis, H., Ciarlet, P.G., Lions, J.L.: Analyse fonctionnelle: théorie et applications, vol. 91. Dunod, Paris (1999)

    Google Scholar 

  6. CGAL, Computational Geometry Algorithms Library. http://www.cgal.org. Accessed 24 Oct 2018

  7. de Goes, F.F.: Geometric discretization through primal-dual meshes. Ph.D. thesis, California Institute of Technology (2014)

  8. De Goes, F., Breeden, K., Ostromoukhov, V., Desbrun, M.: Blue noise through optimal transport. ACM Trans. Graph. (TOG) 31(6), 171 (2012)

    Google Scholar 

  9. Du, Q., Emelianenko, M., Ju, L.: Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Numer. Anal. 44(1), 102–119 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637–676 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  11. Du, Q., Gunzburger, M.: Grid generation and optimization based on centroidal Voronoi tessellations. Appl. Math. Comput. 133(2), 591–607 (2002)

    MathSciNet  MATH  Google Scholar 

  12. Flamary, R., Cuturi, M., Courty, N., Rakotomamonjy, A.: Wasserstein discriminant analysis. arXiv preprint arXiv:1608.08063 (2016)

  13. Graf, S., Luschgy, H.: Foundations of Quantization for Probability Distributions. Springer, Berlin (2007)

    MATH  Google Scholar 

  14. Gruber, P.M.: Optimum quantization and its applications. Adv. Math. 186(2), 456–497 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  15. Henrot, A., Pierre, M.: Variation et optimisation de formes: une analyse géométrique, vol. 48. Springer, Berlin (2006)

    MATH  Google Scholar 

  16. Iri, M., Murota, K., Ohya, T.: A fast Voronoi-diagram algorithm with applications to geographical optimization problems. In: Thoft-Christensen, P. (ed.) System Modelling and Optimization, pp. 273–288. Springer, Berlin (1984)

    Chapter  Google Scholar 

  17. Jordan, R., Kinderlehrer, D., Otto, F.: The variational formulation of the Fokker–Planck equation. SIAM J. Math. Anal. 29(1), 1–17 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kantorovich, L.V.: On a problem of Monge. C. R. (Doklady) Acad. Sci. URSS (NS) 3, 225–226 (1948)

    MathSciNet  Google Scholar 

  19. Kitagawa, J., Mérigot, Q., Thibert, B.: Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. (JEMS) (to appear)

  20. Lévy, B.: A numerical algorithm for l2 semi-discrete optimal transport in 3D. ESAIM Math. Model. Numer. Anal. 49(6), 1693–1715 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Lévy, B., Liu, Y.: \(L_p\) centroidal Voronoi tessellation and its applications. ACM Trans. Graph. (TOG) 29, 1–11 (2010)

    Article  Google Scholar 

  22. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.M., Lu, L., Yang, C.: On centroidal Voronoi tessellation, energy smoothness and fast computation. ACM Trans. Graph. (ToG) 28(4), 101 (2009)

    Article  Google Scholar 

  23. Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. theory 28(2), 129–137 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mérigot, Q.: A comparison of two dual methods for discrete optimal transport. In: Geometric Science of Information, pp. 389–396. Springer (2013)

  25. Mérigot, Q., Meyron, J., Thibert, B.: An algorithm for optimal transport between a simplex soup and a point cloud. SIAM J. Imaging Sci. 11(2), 1363–1389 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  26. Monge, G.: Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris (1781)

  27. Pages, G., Wilbertz, B.: Optimal Delaunay and Voronoi quantization schemes for pricing American style options. In: Carmona, R., Del Moral, P., Hu, P., Oudjane, N. (eds.) Numerical Methods in Finance, pp. 171–213. Springer, Berlin (2012)

    Chapter  Google Scholar 

  28. Rubner, Y., Tomasi, C., Guibas, L.J.: The Earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99–121 (2000)

    Article  MATH  Google Scholar 

  29. Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003)

    Book  MATH  Google Scholar 

  30. Solomon, J., Rustamov, R., Leonidas, G., Butscher, A.: Wasserstein propagation for semi-supervised learning. In: Proceedings of the 31st International Conference on Machine Learning (ICML-14), pp. 306–314 (2014)

  31. Villani, C.: Topics in Optimal Transportation, vol. 58. American Mathematical Society, Providence (2003)

    MATH  Google Scholar 

  32. Wang, W., Slepčev, D., Basu, S., Ozolek, J.A., Rohde, G.K.: A linear optimal transportation framework for quantifying and visualizing variations in sets of images. Int. J. Comput. Vis. 101(2), 254–269 (2013)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut de Mathématiques de Toulouse (UMR 5219), CNRS, INSA, Université de Toulouse, 31077, Toulouse, France

    Frédéric de Gournay & Léo Lebrat

  2. Institut de Mathématiques de Toulouse (UMR 5219), CNRS, UPS, IMT, Université de Toulouse, 31062, Toulouse, France

    Jonas Kahn

Authors
  1. Frédéric de Gournay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jonas Kahn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Léo Lebrat
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frédéric de Gournay.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

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, 429–453 (2019). https://doi.org/10.1007/s00211-018-1000-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-018-1000-4

Mathematics Subject Classification