Widths and rigidity

Yu. V. Malykhin

Sbornik. Mathematics, Tome 215 (2024) no. 4, pp. 543-571

Résumé

We consider the Kolmogorov widths of finite sets of functions. Any orthonormal system of $N$ functions in $L_2$ is rigid, that is, it cannot be well approximated by linear subspaces of dimension essentially smaller than $N$. This is not true for weaker metrics: it is known that in every $L_p$ for $p2$ the first $N$ Walsh functions can be $o(1)$-approximated by a linear space of dimension $o(N)$. We present some sufficient conditions for rigidity. We prove that the independence of functions (in the probabilistic meaning) implies rigidity in $L_1$ and even in $L_0$, the metric that corresponds to convergence in measure. In the case of $L_p$ for $1$ the condition is weaker: any $S_{p'}$-system is $L_p$-rigid. Also we obtain some positive results, for example, that the first $N$ trigonometric functions can be approximated by very low-dimensional spaces in $L_0$, and by subspaces generated by $o(N)$ harmonics in $L_p$ for ${p1}$. Bibliography: 34 titles.

Détail

Keywords: Kolmogorov width, averaged width, matrix rigidity.
Mots-clés : $\mathrm{vc}$-dimension