Widths of some classes of convex functions and bodies

V. N. Konovalov ; V. E. Maiorov

Izvestiya. Mathematics , Tome 74 (2010) no. 1, pp. 127-150.

Résumé

We consider classes of uniformly bounded convex functions defined on convex compact bodies in $\mathbb{R}^d$ and satisfying a Lipschitz condition and establish the exact orders of their Kolmogorov, entropy, and pseudo-dimension widths in the $L_1$-metric. We also introduce the notions of pseudo-dimension and pseudo-dimension widths for classes of sets and determine the exact orders of the entropy and pseudo-dimension widths of some classes of convex bodies in $\mathbb{R}^d$ relative to the pseudo-metric defined as the $d$-dimensional Lebesgue volume of the symmetric difference of two sets. We also find the exact orders of the entropy and pseudo-dimension widths of the corresponding classes of characteristic functions in $L_p$-spaces, $1\le p\le\infty$.

Détail

Keywords: convex function, entropy
Mots-clés : pseudo-dimension.

Bibliographie

[1] V. Maiorov, J. Ratsaby, “On the degree of approximation by manifolds of finite pseudo-dimension”, Constr. Approx., 15:2 (1999), 291–300 | DOI | MR | Zbl

[2] V. N. Konovalov, D. Leviatan, “Kolmogorov and linear widths of weighted Sobolev-type classes on a finite interval. II”, J. Approx. Theory, 113:2 (2001), 266–297 | DOI | MR | Zbl

[3] V. N. Vapnik, A. Ya. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities”, Theory Probab. Appl., 16:2 (1971), 264–280 | DOI | MR | Zbl

[4] D. Haussler, “Decision theoretic generalizations of the PAC model for neural net and other learning applications”, Inform. and Comput., 100:1 (1992), 78–150 | DOI | MR | Zbl

[5] D. Haussler, “Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik–Chervonenkis dimension”, J. Combin. Theory Ser. A, 69:2 (1995), 217–232 | DOI | MR | Zbl

[6] V. Maiorov, J. Ratsaby, “The degree of approximation of sets in Euclidean space using sets with bounded Vapnik–Chervonenkis dimension”, Discrete Appl. Math., 86:1 (1998), 81–93 | DOI | MR | Zbl

[7] V. Maiorov, “Optimal non-linear approximation using sets of finite pseudo-dimension”, East J. Approx., 11:1 (2005), 1–19 | MR | Zbl

[8] A. W. Roberts, D. E. Varberg, Convex functions, Academic Press, New York–London, 1973 | MR | Zbl

[9] X. G. Lu, “On multivariate polynomials convex approximation”, Math. Numer. Sinica, 12:2 (1990), 186–193 | MR | Zbl

[10] B. Carl, “Entropy numbers, $s$-numbers, and eigenvalue problems”, J. Funct. Anal., 41:3 (1981), 290–306 | DOI | MR | Zbl

[11] G. G. Lorentz, M. von Golitschek, Yu. Makovoz, Constructive approximation. Advanced problems, Grundlehren Math. Wiss., 304, Springer-Verlag, Berlin, 1996 | MR | Zbl

[12] V. N. Konovalov, “On the orders of nonlinear approximations for classes of functions of given form”, Math. Notes, 78:1–2 (2005), 88–104 | DOI | MR | Zbl

[13] S. M. Nikolskii, “Ob odnom metode pokrytiya oblasti i neravenstva dlya mnogochlenov ot mnogikh peremennykh”, Mathematica (Cluj), 8:2 (1966), 345–356 | MR | Zbl

[14] S. M. Nikol'skii, “Approximation of functions of several variables by polynomials”, Siberian Math. J., 10:5 (1969), 792–799 | DOI | MR | Zbl

[15] E. M. Bronshteyn, L. D. Ivanov, “The approximation of convex sets by polyhedra”, Siberian Math. J., 16:5 (1975), 852–853 | DOI | MR | Zbl | Zbl

[16] Y. Gordon, M. Meyer, Sh. Reisner, “Volume approximation of convex bodies by polytopes – a constructive method”, Studia Math., 111:1 (1994), 81–95 | MR | Zbl