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.

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: DOI
[1] 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
[2] 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
[3] Benson, R.V., Euclidean geometry and convexity, (1966), McGraw-Hill New York · Zbl 0187.44103
[4] 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
[5] Brauner, H., Differentialgeometrie, (1981), Vieweg Braunschweig
[6] Busemann, H., The foundations of Minkowskian geometry, Comment. math. helv., 24, 156-187, (1950) · Zbl 0040.37502
[7] 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
[8] 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
[9] Conway, J.H.; Sloane, N.J.A., Sphere packings, lattices and groups, (1999), Springer New York · Zbl 0915.52003
[10] 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
[11] Diskant, V.I., Generalizations of a theorem of Lindelöf, Mat. fiz. anal. geom., 4, 59-64, (1997) · Zbl 0908.52003
[12] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellationsapplications and algorithms, SIAM rev., 41, 637-676, (1999) · Zbl 0983.65021
[13] Encyclopedia of Mathematics, Kluwer Academic Publishers, Dordrecht, 1988-1994.
[14] 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
[15] Fejes Tóth, G., A stability criterion to the moment theorem, Studia sci. math. hungar., 34, 209-224, (2001) · Zbl 0997.52007
[16] 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
[17] 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
[18] Gersho, A., Asymptotically optimal block quantization, IEEE trans. inform. theory, IT-25, 373-380, (1979) · Zbl 0409.94013
[19] 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
[20] Graf, S.; Luschgy, H., Foundations of quantization of probability distributions, Lecture notes mathematics, Vol. 1730, (2000), Springer Berlin · Zbl 0951.60003
[21] Gray, R.M.; Neuhoff, D.L., Quantization, IEEE trans. inform. theory, IT-44, 2325-2383, (1998) · Zbl 1016.94016
[22] 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
[23] 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
[24] Gruber, P.M., Volume approximation of convex bodies by circumscribed convex polytopes, Discrete math. theor. comput. sci., 4, 309-317, (1991) · Zbl 0739.52004
[25] 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
[26] Gruber, P.M., Asymptotic estimates for best and stepwise approximation of convex bodies II, Forum math., 5, 383-404, (1993) · Zbl 0889.52006
[27] 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
[28] 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
[29] 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
[30] Gruber, P.M., Optimal configurations of finite point sets in Riemannian 2-manifolds, Geom. dedicata, 84, 271-320, (2001) · Zbl 0982.52020
[31] 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
[32] 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
[33] Gruber, P.M., Optimale quantisierung, Math. semesterber, 49, 227-251, (2003) · Zbl 1032.52001
[34] Hlawka, E., The theory of uniform distribution, (1984), A B Academic Publishers Berkhamsted · Zbl 0585.10035
[35] Holmes, R.D.; Thompson, A.C., N-dimensional area and content in Minkowski spaces, Pacific J. math., 85, 77-110, (1979) · Zbl 0467.51007
[36] Kobayashi, S.; Nomizu, K., Foundations of differential geometry, (1969), Wiley New York · Zbl 0175.48504
[37] 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
[38] 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
[39] 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)
[40] 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
[41] 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
[42] Newman, D.J., The hexagon theorem, IEEE trans. inform. theory, IT-28, 137-139, (1982) · Zbl 0476.94006
[43] 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
[44] Schneider, R., Convex bodies: the brunn-Minkowski theory, (1993), Cambridge University Press Cambridge · Zbl 0798.52001
[45] 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
[46] Sobolev, S.L., Introduction to the theory of cubature formulas, (1974), Nauka Moscow
[47] Thompson, A.C., Minkowski geometry, (1996), Cambridge University Press Cambridge · Zbl 0868.52001
[48] 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.