Asymptotics for Optimal Empirical Quantization of Measures

We investigate the minimal error in approximating a general probability measure μ on Rᵈ by the uniform measure on a finite set with prescribed cardinality n. The error is measured in the p-Wasserstein distance. In particular, when 1≤ p<d, we establish asymptotic upper and lower bounds as n → ∞ on the rescaled minimal error that have the same, explicit dependency on μ. In some instances, we prove that the rescaled minimal error has a limit. These include general measures in dimension $d = 2$ with 1 ≤ p < 2, and uniform measures in arbitrary dimension with 1 ≤ p < d. For some uniform measures, we prove the limit existence for p ≥ d as well. For a class of compactly supported measures with H\"older densities, we determine the convergence speed of the minimal error for every p ≥ 1. Furthermore, we establish a new Pierce-type (i.e., nonasymptotic) upper estimate of the minimal error when 1 ≤ p < d. In the initial sections, we survey the state of the art and draw connections with similar problems, such as classical and random quantization.