Optimum quantization and its applications (Q1877888)

This paper deals with the following problem: Let \(M\) be a \(d\)-dimensional Riemannian manifold, and \(J \subset M\) a set of positive measure. We search for a finite set \(S \subset M\) of cardinality \(n\) so as to minimize \[ \int_J f \left( \min_{p \in S} d(x, p) \right) w(x) d \omega_M(x) \tag{1} \] where \(f\) is an increasing function, \(w: J \rightarrow \mathbb{R}^+\) is some weight function, \(d(x,p)\) is the Riemannian distance between \(x\) and \(p\) and \(d\omega_M\) is the Riemannian volume form on \(M\). Under the assumptions that \(\partial J\) has measure zero, that \(w\) is continuous and for a wide class of functions \(f\) (which includes \(f(t) = t^{\alpha}\) for any \(\alpha > 0\)), the asymptotics of the infimum of (1) over all subsets \(S \subset M\) of size \(n\) is calculated, when \(n \rightarrow \infty\). This infimum is asymptotically equal to \[ \text{div} \left( \int_J w(x)^{\frac{d}{d+\alpha}} d \omega_M(x) \right)^{\frac{d+\alpha}{d}} f \left( \frac{1}{n^{1/d}} \right) \] where \(\alpha\) satisfies \(\lim_{t \rightarrow 0^+} f(st) / f(t) = s^{\alpha}\) for any \(s > 0\) and div is a constant depending solely on \(f\) and \(d\). Related results exist in the literature and are surveyed in the first section of the reviewed paper. Furthermore, denote by \(S_n\) a set \(S \subset M\) of cardinality \(n\) for which (1) is minimal. Then this paper proves that there exists a number \(\delta > 1\), independent of \(n\), such that for every \(n\), any two points of \(S_n\) are of distance at least \(\frac{n^{{1/d}}}{\delta}\) and for any point of \(J\) there exists a point of \(S_n\) which is at most \(\delta n^{1/d}\) far from it. In addition, as \(n \rightarrow \infty\), the set \(S_n\) tends, in the appropriate sense, to be uniformly distributed in \(J\) with density \(w^{\frac{d}{d + \alpha}}\). Different interpretations of these results yield applications to numerical integration, information theory and approximation of convex sets by polytopes.