zbMATH — the first resource for mathematics

On the orders of nonlinear approximations for classes of functions of given form. (English. Russian original) Zbl 1083.41017
Math. Notes 78, No. 1, 88-104 (2005); translation from Mat. Zametki 78, No. 1, 98-114 (2005).
For an interval \(I \subset {\mathbb R}\) and \(s \in {\mathbb N}\), the set \(\Delta_+^s B_q\) is defined as the collection of functions \(f \in L_q(I)\), \(\| f\| _q \leq 1\), for which the divided differences \([f; t_0, \ldots ,t_s]\) are nonnegative for every \(s+1\) points \(t_0, \ldots ,t_s \in I\). Given two subsets, \(W\) and \(G\), of \(L_q\), let \[ E(W,G)_q=\sup_{f \in W}\, \inf_{g \in G} \| f-g\| _q . \] In the paper under review, \(G\) is either the set \(R_n\) of rational functions \(g=u/v\), where \(u,v\) are polynomials of order \(\leq n\), or the set \(\Sigma_{r,n}\) of splines of order \(r\) with \(n-1\) free knots. It is proved that \(E(\Delta_+^s B_\infty, G)_\infty \asymp n^{-1}\) for both \(G=R_n\) and \(G=\Sigma_{r,n}\) if \(s>1\), \(r=1,2, \ldots\) (the case \(s=2\) has been established earlier).
This estimate remains true if \(s=1\), but only for \(G=\Sigma_{r,n}\), whereas \(E(\Delta_+^s B_\infty, R_n)\) does not tend to zero as \(n \to \infty\). In the case of \(W=\Delta_+^s B_q\) with \(q< \infty\), \(E(W,G)_q\) tends to zero for neither \(G=R_n\) nor \(G=\Sigma_{r,n}\).
To compare the above results, the author uses the concept of the so-called pseudodimension of a set of functions. The pseudodimension of \(R_n\) and \(\Sigma_{r,n}\) is \(\asymp n\), and these sets are asymptotically optimal in the sense that \(E(\Delta_+^s B_\infty, G)_\infty \geq c n^{-1}\), with \(c\) independent of \(n\), for any set \(G\) of pseudodimension \(n\).
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
41A15 Spline approximation
41A20 Approximation by rational functions
Full Text: DOI
[1] P. S. Bullen, ”A criterion for n-convexity,” Pacific J. Math., 36 (1971), 81–98. · Zbl 0194.08602
[2] A. W. Roberts and D. E. Varberg, Convex Functions, Academic Press, New York, 1973. · Zbl 0271.26009
[3] J. E. Pecaric and F. Proschan, and Y. L. Tong, Convex Functions, Partial Orderings, and Statistical Applications, Mathematics in Science and Engineering, vol. 187, Academic Press, Boston, 1992.
[4] A. P. Bulanov, ”On the order of approximation of convex functions by rational functions,” Izv. Akad. Nauk SSSR Ser. Mat. [Math. USSR-Izv.], 33 (1969), no. 5, 1132–1148. · Zbl 0194.09402
[5] V. A. Popov and P. P. Petrushev, ”The exact order of best uniform approximation of convex functions by rational functions,” Mat. Sb. [Math. USSR-Sb.], 103 (145) (1977), no. 2 (6), 285–292.
[6] D. Haussler, ”Decision theoretic generalizations of the PAC model for neural net and other learning applications,” Information and Computation, 100 (1992), 78–150. · Zbl 0762.68050 · doi:10.1016/0890-5401(92)90010-D
[7] J. Ratsaby and V. Maiorov, ”Generalization of the PAC model for learning with partial information,” in: Proc. of the 3rd European Conference on Computational Learning Theory (EuroCOLT 97), Springer-Verlag, Berlin, 1997. · Zbl 0894.68063
[8] J. Ratsaby and V. Maiorov, ”On the value of partial information for learning from examples,” J. Complexity, 13 (1997), 509–544. · Zbl 0894.68063 · doi:10.1006/jcom.1997.0459
[9] G. G. Lorentz and M. van Golitschek, and Y. Makovoz, Constructive Approximation, Advanced Problems, Springer-Verlag, New York, 1996. · Zbl 0910.41001
[10] V. Maiorov and J. Ratsa ”The degree of approximation of sets in Euclidian space using sets with bounded Vapnik-Chervonenkis dimension,” Discrete Appl. Math., 88 (1998), 81–93. · Zbl 0908.68149 · doi:10.1016/S0166-218X(98)00015-8
[11] D. Haussler, ”Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension,” J. Combin. Theory. Ser. A, 69 (1995), 217–232. · Zbl 0818.60005 · doi:10.1016/0097-3165(95)90052-7
[12] V. Maiorov and J. Ratsa ”On the degree of approximation by manifolds of finite pseudo-dimension,” Constr. Approximation, 15 (1999), 291–300. · Zbl 0954.41016 · doi:10.1007/s003659900108
[13] V. N. Konovalov, ”Form-preserving widths of Kolmogorov type of classes of s-monotone integrable functions,” Ukrain. Mat. Zh. [Ukrainian Math. J.], 55 (2004), no. 7, 901–926. · Zbl 1079.41025
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.