Approximation by finitely supported measures
ESAIM: Control, Optimisation and Calculus of Variations, Tome 18 (2012) no. 2, pp. 343-359.

We consider the problem of approximating a probability measure defined on a metric space by a measure supported on a finite number of points. More specifically we seek the asymptotic behavior of the minimal Wasserstein distance to an approximation when the number of points goes to infinity. The main result gives an equivalent when the space is a Riemannian manifold and the approximated measure is absolutely continuous and compactly supported.

DOI : 10.1051/cocv/2010100
Classification : 49Q20, 90B85
Mots-clés : measures, Wasserstein distance, quantization, location problem, centroidal Voronoi tessellations 
@article{COCV_2012__18_2_343_0,
     author = {Kloeckner, Beno{\^\i}t},
     title = {Approximation by finitely supported measures},
     journal = {ESAIM: Control, Optimisation and Calculus of Variations},
     pages = {343--359},
     publisher = {EDP-Sciences},
     volume = {18},
     number = {2},
     year = {2012},
     doi = {10.1051/cocv/2010100},
     mrnumber = {2954629},
     zbl = {1246.49040},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/cocv/2010100/}
}
TY  - JOUR
AU  - Kloeckner, Benoît
TI  - Approximation by finitely supported measures
JO  - ESAIM: Control, Optimisation and Calculus of Variations
PY  - 2012
SP  - 343
EP  - 359
VL  - 18
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/cocv/2010100/
DO  - 10.1051/cocv/2010100
LA  - en
ID  - COCV_2012__18_2_343_0
ER  - 
%0 Journal Article
%A Kloeckner, Benoît
%T Approximation by finitely supported measures
%J ESAIM: Control, Optimisation and Calculus of Variations
%D 2012
%P 343-359
%V 18
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/cocv/2010100/
%R 10.1051/cocv/2010100
%G en
%F COCV_2012__18_2_343_0
Kloeckner, Benoît. Approximation by finitely supported measures. ESAIM: Control, Optimisation and Calculus of Variations, Tome 18 (2012) no. 2, pp. 343-359. doi : 10.1051/cocv/2010100. https://www.numdam.org/articles/10.1051/cocv/2010100/

[1] G. Bouchitté, C. Jimenez and M. Rajesh, Asymptotique d'un problème de positionnement optimal. C. R. Math. Acad. Sci. Paris 335 (2002) 853-858. | MR | Zbl

[2] A. Brancolini, G. Buttazzo, F. Santambrogio and E. Stepanov, Long-term planning versus short-term planning in the asymptotical location problem. ESAIM : COCV 15 (2009) 509-524. | Numdam | MR | Zbl

[3] T. Champion, L. De Pascale and P. Juutinen, The ∞-Wasserstein distance : local solutions and existence of optimal transport maps. SIAM J. Math. Anal. 40 (2008) 1-20. | MR | Zbl

[4] V. Dobrić and J.E. Yukich, Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1995) 97-118. | MR | Zbl

[5] Q. Du and D. Wang, The optimal centroidal Voronoi tessellations and the Gersho's conjecture in the three-dimensional space. Comput. Math. Appl. 49 (2005) 1355-1373. | MR | Zbl

[6] Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi tessellations : applications and algorithms. SIAM Rev. 41 (1999) 637-676. | MR | Zbl

[7] K.J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics 85. Cambridge University Press (1986). | MR | Zbl

[8] L. Fejes Tóth, Sur la représentation d'une population infinie par un nombre fini d'éléments. Acta. Math. Acad. Sci. Hungar 10 (1959) 299-304. | MR | Zbl

[9] L. Fejes Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum, Die Grundlehren der mathematischen Wissenschaften, Band 65. Zweite verbesserte und erweiterte Auflage, Springer-Verlag (1972). | MR | Zbl

[10] S. Graf and H. Luschgy, Foundations of quantization for probability distributions, Lecture Notes in Mathematics 1730. Springer-Verlag (2000). | MR | Zbl

[11] J. Heinonen, Lectures on analysis on metric spaces. Universitext, Springer-Verlag (2001). | MR | Zbl

[12] J. Horowitz and R.L. Karandikar, Mean rates of convergence of empirical measures in the Wasserstein metric. J. Comput. Appl. Math. 55 (1994) 261-273. | MR | Zbl

[13] J.E. Hutchinson, Fractals and self-similarity. Indiana Univ. Math. J. 30 (1981) 713-747. | MR | Zbl

[14] F. Morgan and R. Bolton, Hexagonal economic regions solve the location problem. Amer. Math. Monthly 109 (2002) 165-172. | MR | Zbl

[15] S.J.N. Mosconi and P. Tilli, Γ-convergence for the irrigation problem. J. Convex Anal. 12 (2005) 145-158. | MR | Zbl

[16] D.J. Newman, The hexagon theorem. IEEE Trans. Inform. Theory 28 (1982) 137-139. | MR | Zbl

[17] C. Villani, Topics in optimal transportation, Graduate Studies in Mathematics 58. American Mathematical Society (2003). | MR | Zbl

  • Krieg, David; Sonnleitner, Mathias Function recovery on manifolds using scattered data, Journal of Approximation Theory, Volume 305 (2025), p. 106098 | DOI:10.1016/j.jat.2024.106098
  • Motta, Francis C.; McGoff, Kevin; Cummins, Breschine; Haase, Steven B. Generalized measures of population synchrony, Mathematical Biosciences, Volume 380 (2025), p. 109344 | DOI:10.1016/j.mbs.2024.109344
  • Borda, Bence; Grabner, Peter; Matzke, Ryan W. Riesz energy, L2L2 discrepancy, and optimal transport of determinantal point processes on the sphere and the flat torus, Mathematika, Volume 70 (2024) no. 2 | DOI:10.1112/mtk.12245
  • Wang, Feng-Yu; Zhu, Jie-Xiang Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 1 | DOI:10.1214/22-aihp1251
  • Borda, Bence Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 4 | DOI:10.1214/22-aihp1322
  • Kratsios, Anastasis Universal Regular Conditional Distributions via Probabilistic Transformers, Constructive Approximation, Volume 57 (2023) no. 3, p. 1145 | DOI:10.1007/s00365-023-09635-3
  • Riegler, Erwin; Koliander, Günther; Bölcskei, Helmut Lossy compression of general random variables, Information and Inference: A Journal of the IMA, Volume 12 (2023) no. 3, p. 1759 | DOI:10.1093/imaiai/iaac035
  • Li, Huaiqian; Wu, Bingyao Wasserstein Convergence Rates for Empirical Measures of Subordinated Processes on Noncompact Manifolds, Journal of Theoretical Probability, Volume 36 (2023) no. 2, p. 1243 | DOI:10.1007/s10959-022-01196-8
  • Wang, Feng-Yu; Wu, Bingyao Wasserstein Convergence for Empirical Measures of Subordinated Diffusions on Riemannian Manifolds, Potential Analysis, Volume 59 (2023) no. 3, p. 933 | DOI:10.1007/s11118-022-09989-6
  • Wang, Feng-Yu Convergence in Wasserstein distance for empirical measures of semilinear SPDEs, The Annals of Applied Probability, Volume 33 (2023) no. 1 | DOI:10.1214/22-aap1807
  • Reygner, Julien; Touboul, Adrien Reweighting samples under covariate shift using a Wasserstein distance criterion, Electronic Journal of Statistics, Volume 16 (2022) no. 1 | DOI:10.1214/21-ejs1974
  • Amarathunga, Udara; Hogg, Andrew McC.; Rohling, Eelco J.; Roberts, Andrew P.; Grant, Katharine M.; Heslop, David; Hu, Pengxiang; Liebrand, Diederik; Westerhold, Thomas; Zhao, Xiang; Gilmore, Stewart Sill-controlled salinity contrasts followed post-Messinian flooding of the Mediterranean, Nature Geoscience, Volume 15 (2022) no. 9, pp. 720-725 | DOI:10.1038/s41561-022-00998-z
  • Popov, S. V.; Golovina, L. A.; Palcu, D. V.; Goncharova, I. A.; Pinchuk, T. N.; Rostovtseva, Yu. V.; Akhmetiev, M. A.; Aleksandrova, G. N.; Zaporozhets, N. I.; Bannikov, A. F.; Bylinskaya, M. E.; Lazarev, S. Yu. Neogene Regional Scale of the Eastern Paratethys, Stratigraphy and Paleontological Basis, Paleontological Journal, Volume 56 (2022) no. 12, pp. 1557-1720 | DOI:10.1134/s0031030122120024
  • Gallouët, Thomas O.; Mérigot, Quentin; Natale, Andrea Convergence of a Lagrangian Discretization for Barotropic Fluids and Porous Media Flow, SIAM Journal on Mathematical Analysis, Volume 54 (2022) no. 3, p. 2990 | DOI:10.1137/21m1422756
  • Wang, Feng-Yu Wasserstein convergence rate for empirical measures on noncompact manifolds, Stochastic Processes and their Applications, Volume 144 (2022), p. 271 | DOI:10.1016/j.spa.2021.11.006
  • Osman, Mohamed Kamel; Bessedik, Mostefa; Belkebir, Lahcene; Mansouri, Mohamed EI Habib; Atik, Asma; Belkhir, Ayoub; Rubino, Jean-Loup; Satour, Linda; Belhadji, Ahmed Messinian to Piacenzian deposits, erosion, and subsequent marine bioevents in the Dahra Massif (Lower Chelif Basin, Algeria), Arabian Journal of Geosciences, Volume 14 (2021) no. 8 | DOI:10.1007/s12517-021-06481-0
  • Bourne, David P.; Cristoferi, Riccardo Asymptotic Optimality of the Triangular Lattice for a Class of Optimal Location Problems, Communications in Mathematical Physics, Volume 387 (2021) no. 3, p. 1549 | DOI:10.1007/s00220-021-04216-6
  • Ehler, Martin; Gräf, Manuel; Neumayer, Sebastian; Steidl, Gabriele Curve Based Approximation of Measures on Manifolds by Discrepancy Minimization, Foundations of Computational Mathematics, Volume 21 (2021) no. 6, p. 1595 | DOI:10.1007/s10208-021-09491-2
  • Borda, Bence Berry–Esseen Smoothing Inequality for the Wasserstein Metric on Compact Lie Groups, Journal of Fourier Analysis and Applications, Volume 27 (2021) no. 2 | DOI:10.1007/s00041-020-09803-0
  • Iacobelli, Mikaela; Patacchini, Francesco S.; Santambrogio, Filippo Weighted Ultrafast Diffusion Equations: From Well-Posedness to Long-Time Behaviour, Archive for Rational Mechanics and Analysis, Volume 232 (2019) no. 3, p. 1165 | DOI:10.1007/s00205-018-01341-w
  • Weed, Jonathan; Bach, Francis Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, Bernoulli, Volume 25 (2019) no. 4A | DOI:10.3150/18-bej1065
  • Xu, Chuang; Berger, Arno Best finite constrained approximations of one-dimensional probabilities, Journal of Approximation Theory, Volume 244 (2019), p. 1 | DOI:10.1016/j.jat.2019.03.005
  • Le Brigant, Alice; Puechmorel, Stéphane Quantization and clustering on Riemannian manifolds with an application to air traffic analysis, Journal of Multivariate Analysis, Volume 173 (2019), p. 685 | DOI:10.1016/j.jmva.2019.05.008
  • Cañizo, J. A.; Patacchini, F. S. Discrete minimisers are close to continuum minimisers for the interaction energy, Calculus of Variations and Partial Differential Equations, Volume 57 (2018) no. 1 | DOI:10.1007/s00526-017-1289-3
  • Chevallier, Julien Uniform decomposition of probability measures: quantization, clustering and rate of convergence, Journal of Applied Probability, Volume 55 (2018) no. 4, p. 1037 | DOI:10.1017/jpr.2018.69
  • Iacobelli, Mikaela A Gradient Flow Perspective on the Quantization Problem, PDE Models for Multi-Agent Phenomena, Volume 28 (2018), p. 145 | DOI:10.1007/978-3-030-01947-1_7
  • Chauffert, Nicolas; Ciuciu, Philippe; Kahn, Jonas; Weiss, Pierre A Projection Method on Measures Sets, Constructive Approximation, Volume 45 (2017) no. 1, p. 83 | DOI:10.1007/s00365-016-9346-2
  • Mérigot, Quentin; Oudet, Édouard Discrete Optimal Transport: Complexity, Geometry and Applications, Discrete Computational Geometry, Volume 55 (2016) no. 2, p. 263 | DOI:10.1007/s00454-016-9757-7
  • Iacobelli, Mikaela Asymptotic quantization for probability measures on Riemannian manifolds, ESAIM: Control, Optimisation and Calculus of Variations, Volume 22 (2016) no. 3, p. 770 | DOI:10.1051/cocv/2015025
  • Lozar, Francesca; Clari, Pierangelo; Dela Pierre, Francesco; Natalicchio, Marcello; Bernardi, Elisa; Violanti, Donata; Costa, Emanuele; Giardino, Marco Virtual Tour of Past Environmental and Climate Change: the Messinian Succession of the Tertiary Piedmont Basin (Italy), Geoheritage, Volume 7 (2015) no. 1, pp. 47-56 | DOI:10.1007/s12371-014-0098-8
  • Guibas, Leonidas J.; Mérigot, Quentin; Morozov, Dmitriy Witnessed k-Distance, arXiv (2011) | DOI:10.48550/arxiv.1102.4972 | arXiv:1102.4972

Cité par 31 documents. Sources : Crossref, NASA ADS