Geodesic
Widths and rigidity
Sbornik. Mathematics, Tome 215 (2024) no. 4, pp. 543-571 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $p<2$ 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 ${p<1}$. Bibliography: 34 titles.
Keywords: Kolmogorov width, averaged width, matrix rigidity.
Mots-clés : $\mathrm{vc}$-dimension 
@article{SM_2024_215_4_a4,
     author = {Yu. V. Malykhin},
     title = {Widths and rigidity},
     journal = {Sbornik. Mathematics},
     pages = {543--571},
     year = {2024},
     volume = {215},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2024_215_4_a4/}
}
TY  - JOUR
AU  - Yu. V. Malykhin
TI  - Widths and rigidity
JO  - Sbornik. Mathematics
PY  - 2024
SP  - 543
EP  - 571
VL  - 215
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2024_215_4_a4/
LA  - en
ID  - SM_2024_215_4_a4
ER  - 
%0 Journal Article
%A Yu. V. Malykhin
%T Widths and rigidity
%J Sbornik. Mathematics
%D 2024
%P 543-571
%V 215
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2024_215_4_a4/
%G en
%F SM_2024_215_4_a4
Yu. V. Malykhin. Widths and rigidity. Sbornik. Mathematics, Tome 215 (2024) no. 4, pp. 543-571. http://geodesic.mathdoc.fr/item/SM_2024_215_4_a4/

[1] A. Kolmogoroff (Kolmogorov), “Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse”, Ann. of Math. (2), 37:1 (1936), 107–110 | DOI | MR | MR | Zbl | Zbl

[2] G. G. Lorentz, M. von Golitschek and Y. Makovoz, Constructive approximation. Advanced problems, Grundlehren Math. Wiss., 304, Springer-Verlag, Berlin, 1996, xii+649 pp. | MR | Zbl

[3] A. Pinkus, $n$-widths in approximation theory, Ergeb. Math. Grenzgeb. (3), 7, Springer-Verlag, Berlin, 1985, x+291 pp. | DOI | MR | Zbl

[4] Dinh Dũng, V. Temlyakov and T. Ullrich, Hyperbolic cross approximation, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Cham, 2018, xi+218 pp. | DOI | MR | Zbl

[5] V. M. Tikhomirov, “Approximation theory”, Analysis, v. II, Encyclopaedia Math. Sci., 14, Convex analysis and approximation theory, Springer-Verlag, Berlin, 1990, 93–243 | DOI | MR | Zbl

[6] Y. Malykhin, “Matrix and tensor rigidity and $L_p$-approximation”, J. Complexity, 72 (2022), 101651, 13 pp. | DOI | MR | Zbl

[7] S. V. Lokam, “Complexity lower bounds using linear algebra”, Found. Trends Theor. Comput. Sci., 4:1–2 (2008), 1–155 | DOI | MR | Zbl

[8] J. Alman and R. Williams, “Probabilistic rank and matrix rigidity”, STOC'17 Proceedings of the 49th annual ACM SIGACT symposium on theory of computing (Montreal, QC 2017), ACM, New York, 2017, 641–652 | DOI | MR | Zbl

[9] S. M. Voronin and N. Temirgaliev, “On some applications of Banach measure”, Izv. Akad. Nauk Kaz. SSR, Ser. Fiz.-Mat., 1984, no. 5, 8–11 (Russian) | MR | Zbl

[10] V. E. Maĭorov, “Kolmogorov's $(n,\delta)$-widths of spaces of smooth functions”, Russian Acad. Sci. Sb. Math., 79:2 (1994), 265–279 | DOI | MR | Zbl

[11] J. Creutzig, “Relations between classical, average, and probabilistic Kolmogorov widths”, J. Complexity, 18:1 (2002), 287–303 | DOI | MR | Zbl

[12] B. S. Kashin, “Lower bounds for $m$-term approximations in the metric of the discrete space $L_n^0$”, Russian Math. Surveys, 76:5 (2021), 933–935 | DOI | MR | Zbl

[13] V. F. Gaposhkin, “Lacunary series and independent functions”, Russian Math. Surveys, 21:6 (1966), 1–82 | DOI | MR | Zbl

[14] B. S. Kashin, Yu. V. Malykhin and K. S. Ryutin, “Kolmogorov width and approximate rank”, Proc. Steklov Inst. Math., 303 (2018), 140–153 | DOI | MR | Zbl

[15] J. Bourgain, “Bounded orthogonal systems and the $\Lambda(p)$-set problem”, Acta Math., 162:3–4 (1989), 227–245 | DOI | MR | Zbl

[16] Z. Dvir and A. Liu, “Fourier and circulant matrices are not rigid”, 34th computational complexity conference, LIPIcs. Leibniz Int. Proc. Inform., 137, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, 17, 23 pp. | DOI | MR | Zbl

[17] V. I. Ivanov and V. A. Yudin, “Trigonometric system in $L_p$, $0

1$”, Math. Notes, 28:6 (1980), 884–889 | DOI | MR | Zbl

[18] T. Oikhberg and M. I. Ostrovskii, “Dependence of Kolmogorov widths on the ambient space”, Zh. Mat. Fiz. Anal. Geom., 9:1 (2013), 25–50 | MR | Zbl

[19] E. Novak and H. Woźniakowski, Tractability of multivariate problems, v. I, EMS Tracts Math., 6, Linear information, Eur. Math. Soc., Zürich, 2008, xii+384 pp. | DOI | MR | Zbl

[20] R. S. Ismagilov, “On $n$-dimensional diameters of compacts in a Hilbert space”, Funct. Anal. Appl., 2:2 (1968), 125–132 | DOI | MR | Zbl

[21] N. N. Vakhania, V. I. Tarieladze and S. A. Chobanyan, Probability distributions on Banach spaces, Math. Appl. (Soviet Ser.), 14, D. Reidel Publishing Co., Dordrecht, 1987, xxvi+482 pp. | DOI | MR | MR | Zbl | Zbl

[22] R. Vershynin, High-dimensional probability. An introduction with applications in data science, Camb. Ser. Stat. Probab. Math., 47, Cambridge Univ. Press, Cambridge, 2018, xiv+284 pp. | DOI | MR | Zbl

[23] J. D. Vaaler, “A geometric inequality with applications to linear forms”, Pacific J. Math., 83:2 (1979), 543–553 | DOI | MR | Zbl

[24] S. Mendelson and R. Vershynin, “Entropy and the combinatorial dimension”, Invent. Math., 152:1 (2003), 37–55 | DOI | MR | Zbl

[25] N. Alon, P. Frankl and V. R{o}dl, “Geometrical realization of set systems and probabilistic communication complexity”, SFCS'85 Proceedings of the 26th annual symposium on foundations of computer science (Portland, OR 1985), IEEE Computer Soc., Washington, DC, 1985, 277–280 | DOI

[26] N. Alon, S. Moran and A. Yehudayoff, “Sign rank versus VC dimension”, 29th annual conference on learning theory, Proceedings of Machine Learning Research (PMLR), 49, 2016, 47–80, https://proceedings.mlr.press/v49/alon16.html

[27] B. S. Kashin and A. A. Saakyan, Orthogonal series, Transl. Math. Monogr., 75, Amer. Math. Soc., Providence, RI, 1989, xii+451 pp. | DOI | MR | MR | Zbl | Zbl

[28] I. Berkes, “On the uniform theory of lacunary series”, Number theory — Diophantine problems, uniform distribution and applications, Springer, Cham, 2017, 137–167 | DOI | MR | Zbl

[29] S. V. Astashkin, The Rademacher system in function spaces, Birkhäuser/Springer, Cham, 2020, xx+559 pp. | DOI | MR | Zbl | Zbl

[30] C. Bennett and K. Rudnick, On Lorentz–Zygmund spaces, Dissertationes Math. (Rozprawy Mat.), 175, PWN, Warszawa, 1980, 67 pp. | MR | Zbl

[31] E. D. Gluskin, “Intersections of a cube with an octahedron are poorly approximated by subspaces of small dimension”, Approximation of functions by special classes of operators, Interuniv. Collect. Sci. Works, Min. pros. RSFSR, Vologod. Gos. Ped. Inst., Vologda, 1987, 35–41 (Russian) | MR | Zbl

[32] D. J. Hajela, “Construction techniques for some thin sets in duals of compact abelian groups”, Ann. Inst. Fourier (Grenoble), 36:3 (1986), 137–166 | DOI | MR | Zbl

[33] B. S. Kashin, “The diameters of octahedra”, Uspekhi Mat. Nauk, 30:4(184) (1975), 251–252 (Russian) | MR | Zbl

[34] Terence Tao and Van H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Reprint of the 2006 ed., Cambridge Univ. Press, Cambridge, 2010, xviii+512 pp. | DOI | MR | Zbl