On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

Abstract.

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class $\cal H$ of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width $\rho_n({\cal F}, L_q)$ = $inf_{{\cal H}^n} \mbox{dist}({\cal F}, {\cal H}^n, L_q)$ which measures the worst-case approximation error over all functions $f\in {\cal F}$ by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , $1 \leq p, q \leq \infty$ . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators.