On the orders of nonlinear approximations for classes of functions of given form
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\).
- Impact of the shape of functions on the orders of piecewise polynomial and rational approximation
- scientific article; zbMATH DE number 1802666
- Non-linear approximation of functions with mixed smoothness by sets of finite pseudo-dimension
- On the degree of approximation by manifolds of finite pseudo-dimension
- Entropy number and non-linear approximations on multivariate Besov space by manifolds of finite pseudo-dimension
- A criterion for n-convexity
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- scientific article; zbMATH DE number 3425889 (Why is no real title available?)
- scientific article; zbMATH DE number 713342 (Why is no real title available?)
- scientific article; zbMATH DE number 3308539 (Why is no real title available?)
- On the degree of approximation by manifolds of finite pseudo-dimension
- On the value of partial information for learning from examples
- Shape-preserving Kolmogorov widths of classes of s-monotone integrable functions
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
This page was built for publication: On the orders of nonlinear approximations for classes of functions of given form
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2577348)
