Optimum quantization and its applications
type: Item
instance of: scholarly article
title: Optimum quantization and its applications
zbMATH Open document ID: 1062.94012
author: Peter M. Gruber
published in: Advances in Mathematics
publication date: 2004-08-19T00:00:00Z
review text: 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 pol…
Mathematics Subject Classification ID: 94A24
Mathematics Subject Classification ID: 53C20
Mathematics Subject Classification ID: 94A34
Mathematics Subject Classification ID: 65D30
Mathematics Subject Classification ID: 65D32
Mathematics Subject Classification ID: 52A27
Mathematics Subject Classification ID: 52B60
zbMATH DE Number: 2093019
zbMATH Keywords: Optimum quantization
zbMATH Keywords: Sums of moments
zbMATH Keywords: Distortion of vector quantizers
zbMATH Keywords: Approximation of probability measures
zbMATH Keywords: Error of numerical integration formulae
zbMATH Keywords: Best approximating polytopes
zbMATH Keywords: Minimum isoperimetric quotient
reviewed by: B. Klartag
MaRDI profile type: Publication
full work available at URL: j.aim.2003.07.017
OpenAlex ID: W1980999467
cites work: Asymptotically sharp bounds for the remainder for the best quadrature formulas for several classes of functions
cites work: On the optimal error bound for cubature formulae on certain classes of continuous functions
cites work: Q5581251
cites work: The error of polytopal approximation with respect to the symmetric difference metric and the \(L_p\) metric
cites work: Q3918679
cites work: The foundations of Minkowskian geometry
cites work: Q4380887
cites work: Q4885026
cites work: Q4219187
cites work: Q5748523
cites work: Q3840059
cites work: Centroidal Voronoi Tessellations: Applications and Algorithms
cites work: The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
cites work: A stability criterion to the moment theorem
cites work: Sur la représentation d'une population infinie par un nombre fini d'éléments
cites work: Q5824053
cites work: Asymptotically optimal block quantization
cites work: Asymptotic estimates for best and stepwise approximation of convex bodies III
cites work: Foundations of quantization for probability distributions
cites work: Quantization
cites work: Process definitions of distortion-rate functions and source coding theorems
cites work: A generalization of Ornstein's \(\overline d\) distance with applications to information theory
cites work: Q3974974
cites work: Q4274007
cites work: Q4368920
cites work: Optimal arrangement of finite point sets in Riemannian 2-manifolds
cites work: A short analytic proof of Fejes Tóth's theorem on sums of moments
cites work: Optimal configurations of finite sets in Riemannian 2-manifolds
cites work: Error of asymptotic formulae for volume approximation of convex bodies in \({\mathbb E}^d\)
cites work: Q4681907
cites work: Optimal quantization
cites work: Q3710597
cites work: N-dimensional area and content in Minkowski spaces
cites work: Q5565587
cites work: Q3218572
cites work: Fixed rate universal block source coding with a fidelity criterion
cites work: The hexagon theorem
cites work: Asymptotically optimal cubature weight formulas
cites work: Q5287551
cites work: Quadrature formulae for functions of several variables satisfying a general Lipschitz condition
cites work: Q4716272
cites work: Asymptotic quantization error of continuous signals and the quantization dimension
DOI: 10.1016/J.AIM.2003.07.017
Recommended article: Optimal quantization
Recommended article: Optimal approximation and quantisation
Recommended article: Optimal quantization via dynamics
Recommended article: On the design of an optimal quantizer
Recommended article: An Optimization Approach to Single-Bit Quantization
Recommended article: Fast approximations to discrete optimal quantization
Recommended article: On asymptotic sufficiency and optimality of quantizations
Recommended article: Some remarks on the existence of optimal quantizers
Recommended article: Optimum orthogonal quantization of signal space (Corresp.)