Kolmogorov, Linear and Pseudo-Dimensional Widths of Classes of s-Monotone Functions in Lp , 0 < p < 1

Konovalov, Victor N. ; Kopotun, Kirill A.

Canadian mathematical bulletin, Tome 51 (2008) no. 2, pp. 236-248

Résumé

Let ${{B}_{p}}$ be the unit ball in ${{\mathbb{L}}_{p}}$ , $0\,<\,p\,<\,1$ , and let $\Delta _{+}^{s}$ , $s\,\in \,\mathbb{N}$ , be the set of all $s$ -monotone functions on a finite interval $I$ , i.e., $\Delta _{+}^{s}$ consists of all functions $x\,:\,I\,\mapsto \,\mathbb{R}$ such that the divided differences $[x;\,{{t}_{0}},\,...\,,\,{{t}_{s}}]$ of order $s$ are nonnegative for all choices of $\left( s\,+\,1 \right)$ distinct points ${{t}_{0}},\,.\,.\,.\,,{{t}_{s}}\,\in \,I.$ For the classes $\Delta _{+}^{s}{{B}_{P}}\,:=\,\Delta _{+}^{s}\,\cap \,{{B}_{P}},$ we obtain exact orders of Kolmogorov, linear and pseudo-dimensional widths in the spaces ${{\mathbb{L}}_{q}},$ $0\,<\,q\,<\,p\,<\,1$ : $${{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{psd}}\asymp {{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{kol}}\asymp {{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{lin}}\asymp {{n}^{-s}}.$$

Détail

DOI : 10.4153/CMB-2008-025-6

Mots-clés : 41A46, 46E35, 41A29, Kolmogorov width, linear width, pseudo-dimensional widths, s-monotone functions

Bibliographie

[1] [1] Bullen, P. S., A criterion for n-convexity. Pacific J. Math. 36(1971), 81–98. Google Scholar

[2] [2] DeVore, R. A. and Lorentz, G. G., Constructive approximation. Grundlehren Math. Wiss. 303, Springer–Verlag, Berlin, 1993. Google Scholar

[3] [3] Ditzian, Z., Konovalov, V. N. and Leviatan, D., Approximation of Sobolev-type classes with quasi-seminorms. Rocky Mountain J. Math. 35(2005), 445–478. Google Scholar

[4] [4] Dyn, N., Lorentz, G. G. and Riemenschneider, S. D., Continuity of the Birkhoff interpolation. SIAM J. Numer. Anal. 19(1982), 507–509. Google Scholar

[5] [5] Hardy, G. H., Littlewood, J. E. and Pólya, G., Inequalities. Second edition, Cambridge University Press, 1952. Google Scholar

[6] [6] Haussler, D., Decision-theoretic generalizations of the PAC model for neural net and other learning applications. Inform. and Comput. 100(1992), 78–150. Google Scholar

[7] [7] Konovalov, V. N. and Leviatan, D., Shape preserving widths of Sobolev-type classes of s-monotone functions on a finite interval. Israel J. Math. 133(2003), 239–268. Google Scholar

[8] [8] Kopotun, K. A., Whitney theorem of interpolatory type for k-monotone functions. Constr. Approx. 17(2001), 307–317. Google Scholar

[9] [9] Kopotun, K. and Shadrin, A., On k-monotone approximation by free knot splines. SIAM J. Math. Anal. 34(2003), 901–924 (electronic). Google Scholar

[10] [10] Lorentz, G. G., Golitschek, M. v. and Makovoz, Y., Constructive approximation. Advanced problems. GrundlehrenMath.Wiss. 304, Springer–Verlag, Berlin, 1996. Google Scholar

[11] [11] Maiorov, V. and Ratsaby, J., The degree of approximation of sets in Euclidean space using sets with bounded Vapnik–Chervonenkis dimension. Discrete Appl. Math. 86(1998), 81–93. Google Scholar

[12] [12] Maiorov, V. and Ratsaby, J., On the degree of approximation by manifolds of finite pseudo-dimension. Constr. Approx. 15(1999), 291–300 Google Scholar

[13] [13] Pollard, D., Convergence of stochastic processes. Springer Series in Statistics, Springer–Verlag, New York, 1984. Google Scholar

[14] [14] Pečarić, J. E., Proschan, F. and Tong, Y. L., Convex functions, partial orderings, and statistical applications. Mathematics in Science and Engineering 187, Academic Press Inc., Boston, MA, 1992. Google Scholar

[15] [15] Ratsaby, J. and Maiorov, V., Generalization of the PAC-model for learning with partial information (extended abstract). In: Computational learning theory (Jerusalem, 1997), Lecture Notes in Comput. Sci. 1208(1997), 51–65. Google Scholar

[16] [16] Roberts, A. W. and Varberg, D. E., Convex functions. Pure and Applied Mathematics 57, Academic Press, New York–London, 1973. Google Scholar

[17] [17] Wenocur, R. S. and Dudley, R. M., Some special Vapnik–Chervonenkis classes. Discrete Math. 33(1981), 313–318. Google Scholar