|
Widths related to pseudo-dimension
Yu. V. Malykhin M. V. Lomonosov Moscow State University
Abstract:
We consider two widths related to the notion of pseudo-dimension. The first is $\rho_n$, which is defined in a similar way to Kolmogorov's width but replacing the linear dimension by the pseudo-dimension. $\rho_n$ can be bounded below by the second width $s_n$, which is half of the length of the maximal edge of the $(n+1)$-dimensional ‘coordinate’ cube inscribed in the given set in a special way. We construct examples of sets for which the ratios $\rho_n/s_n$ (for $n\geqslant 2$) and $\rho_{10n}/s_{9n}$ (for a sufficiently large $n$) are as large as desired. In terms of combinatorial dimension, the main result means that for any $C>0$ and any sufficiently large $n$ there is a set $W$ of dimension $\mathrm{vc}(W,1)\leqslant 9n$ which cannot be approximated with respect to the uniform norm with accuracy $C$ by any set $V$ of dimension $\mathrm{vc}(V,0)\leqslant 10n$.
Keywords:
VC-dimension, combinatorial dimension, widths.
Received: 11.04.2007
Citation:
Yu. V. Malykhin, “Widths related to pseudo-dimension”, Izv. Math., 73:2 (2009), 319–332
Linking options:
https://www.mathnet.ru/eng/im2648https://doi.org/10.1070/IM2009v073n02ABEH002448 https://www.mathnet.ru/eng/im/v73/i2/p109
|
|