# zbMATH — the first resource for mathematics

Optimum quantization and its applications. (English) Zbl 1062.94012
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.

##### MSC:
 94A24 Coding theorems (Shannon theory) 53C20 Global Riemannian geometry, including pinching 94A34 Rate-distortion theory in information and communication theory 65D30 Numerical integration 65D32 Numerical quadrature and cubature formulas 52A27 Approximation by convex sets 52B60 Isoperimetric problems for polytopes
Full Text:
##### References:
  Babenko, V.F., Asymptotically sharp bounds for the remainder for the best quadrature formulas for several classes of functions, Mat. zametki, 19, 313-322;, (1976), Math. Notes 19 (1976) 187-193 · Zbl 0333.41024  Babenko, V.F., On the optimal error bound for cubature formulas on certain classes of continuous functions, Anal. math., 3, 3-9, (1977) · Zbl 0372.41020  Benson, R.V., Euclidean geometry and convexity, (1966), McGraw-Hill New York · Zbl 0187.44103  Böröczky, K., The error of polytopal approximation with respect to the symmetric difference metric and the Lp metric, Israel J. math., 117, 1-28, (2000) · Zbl 0986.52004  Brauner, H., Differentialgeometrie, (1981), Vieweg Braunschweig  Busemann, H., The foundations of Minkowskian geometry, Comment. math. helv., 24, 156-187, (1950) · Zbl 0040.37502  Chernaya, E.V., An asymptotic sharp estimate for the remainder of weighted cubature formulas that are optimal on certain classes of continuous functions, Ukraı̈n. mat. zh., 47, 1405-1415;, (1995), Ukrainian J. Math. 47 (1995) 1606-1618 · Zbl 0886.41023  Chernaya (=Chornaya), E.V., On the optimization of weighted cubature formulae on certain classes of continuous functions, East J. approx., 1, 47-60, (1995) · Zbl 0848.41023  Conway, J.H.; Sloane, N.J.A., Sphere packings, lattices and groups, (1999), Springer New York · Zbl 0915.52003  Diskant, V.I., Making precise the isoperimetric inequality and stability theorems in the theory of convex bodies, Trudy inst. mat. (Novosibirsk), 14, 98-132, (1989) · Zbl 0717.52009  Diskant, V.I., Generalizations of a theorem of Lindelöf, Mat. fiz. anal. geom., 4, 59-64, (1997) · Zbl 0908.52003  Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellationsapplications and algorithms, SIAM rev., 41, 637-676, (1999) · Zbl 0983.65021  Encyclopedia of Mathematics, Kluwer Academic Publishers, Dordrecht, 1988-1994.  Ewald, G.; Larman, D.; Rogers, C.A., The direction of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space, Mathematika, 17, 1-20, (1970) · Zbl 0199.57002  Fejes Tóth, G., A stability criterion to the moment theorem, Studia sci. math. hungar., 34, 209-224, (2001) · Zbl 0997.52007  Fejes Tóth, L., Sur la représentation d’une population infinie par un nombre fini d’elements, Acta math. acad. sci. hungar., 10, 299-304, (1959) · Zbl 0094.35303  L. Fejes Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum, 1st Edition, 1953, 2nd edition. Springer, Berlin, 1972. · Zbl 0052.18401  Gersho, A., Asymptotically optimal block quantization, IEEE trans. inform. theory, IT-25, 373-380, (1979) · Zbl 0409.94013  Glasauer, S.; Gruber, P.M., Asymptotic estimates for best and stepwise approximation of convex bodies III, Forum math., 9, 383-404, (1997) · Zbl 0889.52006  Graf, S.; Luschgy, H., Foundations of quantization of probability distributions, Lecture notes mathematics, Vol. 1730, (2000), Springer Berlin · Zbl 0951.60003  Gray, R.M.; Neuhoff, D.L., Quantization, IEEE trans. inform. theory, IT-44, 2325-2383, (1998) · Zbl 1016.94016  Gray, R.M.; Neuhoff, D.L.; Omura, J.K., Process definitions of distortion rate functions and source coding theorems, IEEE trans. inform. theory, IT-21, 524-532, (1975) · Zbl 0313.94008  Gray, R.M.; Neuhoff, D.L.; Shields, P.C., A generalization of Ornstein’s d-bar distance with applications to information theory, Ann. probab., 3, 315-328, (1975) · Zbl 0304.94025  Gruber, P.M., Volume approximation of convex bodies by circumscribed convex polytopes, Discrete math. theor. comput. sci., 4, 309-317, (1991) · Zbl 0739.52004  P.M. Gruber, Aspects of approximation of convex bodies, in: P.M. Gruber, J.M. Wills (Eds.), Handbook of Convex Geometry A, North-Holland, Amsterdam, 1993, pp. 319-345. · Zbl 0791.52007  Gruber, P.M., Asymptotic estimates for best and stepwise approximation of convex bodies II, Forum math., 5, 383-404, (1993) · Zbl 0889.52006  Gruber, P.M., Comparisons of best and random approximation of convex bodies by convex polytopes, Rend. sem. mat. univ. Palermo, ser. II, 50, Suppl., 189-216, (1997) · Zbl 0896.52014  Gruber, P.M., Optimal arrangements of finite point sets in Riemannian 2-manifolds, Trudy mat. inst. Steklov., 225, 148-155;, (1999), Proc. Steklov Math. Inst. 225 (1999) 160-167 · Zbl 0982.52021  Gruber, P.M., A short analytic proof of fejes Tóth’s theorem on sums of moments, Aequationes math., 58, 291-295, (1999) · Zbl 1006.52015  Gruber, P.M., Optimal configurations of finite point sets in Riemannian 2-manifolds, Geom. dedicata, 84, 271-320, (2001) · Zbl 0982.52020  Gruber, P.M., Error of asymptotic formulae for volume approximation of convex bodies in $$E\^{}\{d\}$$, Monatsh. math., 135, 279-304, (2002) · Zbl 1006.52002  Gruber, P.M., Error of asymptotic formulae for volume approximation of convex bodies in $$E\^{}\{3\}$$, Trudy mat. inst. Steklov., 239, 106-117;, (2002), Proc. Steklov Math. Inst. 239 (2002) 96-107  Gruber, P.M., Optimale quantisierung, Math. semesterber, 49, 227-251, (2003) · Zbl 1032.52001  Hlawka, E., The theory of uniform distribution, (1984), A B Academic Publishers Berkhamsted · Zbl 0585.10035  Holmes, R.D.; Thompson, A.C., N-dimensional area and content in Minkowski spaces, Pacific J. math., 85, 77-110, (1979) · Zbl 0467.51007  Kobayashi, S.; Nomizu, K., Foundations of differential geometry, (1969), Wiley New York · Zbl 0175.48504  M. Kuczma, An Introduction to the Theory of Functional Equations and Inequalities (Cauchy’s equation and Jensen’s inequality), PWN, Warszawa, 1985. · Zbl 0555.39004  Lindelöf, L., Propriétés générales des polyèdres qui, sous une étendue superficielle donnée, renferment le plus grand volume, Saint |St. Petersburg bull. acad. sci., 14, 258-269;, (1869), Math. Ann. 2 (1870) 150-159 · JFM 02.0425.01  Matérn, B.; Persson, O., On the extremum properties of the equilateral triangular lattice and the regular hexagonal network, Förtech. över. rapp. Uppsala Stockholm, 7, 15, (1965)  Minkowski, H., Allgemeine lehrsätze über die convexen polyeder, Nachr. kgl. ges. wiss. Göttingen math.-phys. kl., 1897, 198-219;, (1911), Ges. Abh. 2 (1911) 103-121 · JFM 28.0427.01  Neuhoff, D.L.; Gray, R.M.; Davisson, L.D., Fixed rate universal block source coding with a fidelity criterion, IEEE trans. inform. theory, IT-21, 511-523, (1975) · Zbl 0313.94007  Newman, D.J., The hexagon theorem, IEEE trans. inform. theory, IT-28, 137-139, (1982) · Zbl 0476.94006  Polovinkin, V.I., Asymptotically optimal cubature weight formulas, Sibirskiı̆ mat. zh., 70, 151-160;, (1989), Siber. Math. J. 70 (1989) 289-297 · Zbl 0708.41024  Schneider, R., Convex bodies: the brunn-Minkowski theory, (1993), Cambridge University Press Cambridge · Zbl 0798.52001  Sobol’, I.M., Quadrature formulas for functions in several variables that satisfy the general Lipschitz condition, Zh. vychisl. mat. i mat. fiz., 29, 935-941;, (1989), U.S.S.R. Comput. Math. Math. Phys. 29 (1989) 201-206  Sobolev, S.L., Introduction to the theory of cubature formulas, (1974), Nauka Moscow  Thompson, A.C., Minkowski geometry, (1996), Cambridge University Press Cambridge · Zbl 0868.52001  Zador, P.L., Asymptotic quantization error of continuous signals and the quantization dimension, IEEE trans. inform. theory, IT-28, 139-148, (1982) · Zbl 0476.94008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.