Geodesic
Kolmogorov width and approximate rank
Informatics and Automation, Harmonic analysis, approximation theory, and number theory, Tome 303 (2018), pp. 155-168.

Voir la notice de l'article provenant de la source Math-Net.Ru

Closely related notions of the Kolmogorov width and the approximate rank of a matrix are considered. New estimates are established in approximation problems related to the width of the set of characteristic functions of intervals; the multidimensional case (characteristic functions of parallelepipeds) is also considered. 
@article{TRSPY_2018_303_a11,
     author = {B. S. Kashin and Yu. V. Malykhin and K. S. Ryutin},
     title = {Kolmogorov width and approximate rank},
     journal = {Informatics and Automation},
     pages = {155--168},
     publisher = {mathdoc},
     volume = {303},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2018_303_a11/}
}
TY  - JOUR
AU  - B. S. Kashin
AU  - Yu. V. Malykhin
AU  - K. S. Ryutin
TI  - Kolmogorov width and approximate rank
JO  - Informatics and Automation
PY  - 2018
SP  - 155
EP  - 168
VL  - 303
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2018_303_a11/
LA  - ru
ID  - TRSPY_2018_303_a11
ER  - 
%0 Journal Article
%A B. S. Kashin
%A Yu. V. Malykhin
%A K. S. Ryutin
%T Kolmogorov width and approximate rank
%J Informatics and Automation
%D 2018
%P 155-168
%V 303
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2018_303_a11/
%G ru
%F TRSPY_2018_303_a11
B. S. Kashin; Yu. V. Malykhin; K. S. Ryutin. Kolmogorov width and approximate rank. Informatics and Automation, Harmonic analysis, approximation theory, and number theory, Tome 303 (2018), pp. 155-168. http://geodesic.mathdoc.fr/item/TRSPY_2018_303_a11/

[1] Alon N., “Perturbed identity matrices have high rank: proof and applications”, Comb. Probab. Comput., 18:1–2 (2009), 3–15 | DOI | MR | Zbl

[2] Alon N., Klartag B., Optimal compression of approximate inner products and dimension reduction, E-print, 2016, arXiv: 1610.00239 [math.MG] | MR

[3] Alon N., Lee T., Shraibman A., Vempala S., “The approximate rank of a matrix and its algorithmic applications: approximate rank”, Proc. 45th Annu. ACM Symp. on Theory of Computing (Palo Alto, CA (USA), 2013), ACM, New York, 2013, 675–684 | DOI | MR | Zbl

[4] N. K. Bary, A Treatise on Trigonometric Series, v. I, II, Pergamon, Oxford, 1964 | MR | Zbl

[5] E. S. Belinskii, “Approximation of periodic functions by a ‘floating’ system of exponentials, and trigonometric widths”, Studies on the Theory of Functions of Many Real Variables, Yaroslav. Gos. Univ., Yaroslavl, 1984, 10–24 (in Russian)

[6] DeVore R. A., Temlyakov V. N., “Nonlinear approximation by trigonometric sums”, J. Fourier Anal. Appl., 2:1 (1995), 29–48 | DOI | MR | Zbl

[7] Forster J., Schmitt N., Simon H. U., Suttorp T., “Estimating the optimal margins of embeddings in Euclidean half spaces”, Mach. Learn., 51:3 (2003), 263–281 | DOI | MR | Zbl

[8] E. D. Gluskin, “Norms of random matrices and widths of finite-dimensional sets”, Math. USSR, Sb., 48:1 (1984), 173–182 | DOI | MR | Zbl | Zbl

[9] E. D. Gluskin, “The octahedron is badly approximated by random subspaces”, Funct. Anal. Appl., 20:1 (1986), 11–16 | DOI | MR | Zbl

[10] Grafakos L., Classical Fourier analysis, 3rd ed., Springer, New York, 2014 | MR | Zbl

[11] G. H. Hardy, J. E. Littlewood, G. Pólya, Inequalities, Univ. Press, Cambridge, 1934 | MR

[12] R. S. Ismagilov, “Diameters of sets in normed linear spaces and the approximation of functions by trigonometric polynomials”, Russ. Math. Surv., 29:3 (1974), 169–186 | DOI | MR | Zbl

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

[14] B. S. Kashin, “Diameters of some finite-dimensional sets and classes of smooth functions”, Math. USSR, Izv., 11:2 (1977), 317–333 | DOI | MR | Zbl | Zbl

[15] B. S. Kashin, “On certain properties of matrices of bounded operators from $\ell _2^n$ into $\ell _2^m$”, Izv. Akad. Nauk Arm. SSR, 15:5 (1980), 379–394 | MR | Zbl

[16] B. S. Kashin, “Lower bounds for $n$-term approximations of plane convex sets and related topics”, Math. Notes, 72:4 (2002), 473–478 | DOI | DOI | MR | Zbl

[17] B. S. Kashin, “Remark on estimates of orthomassivity”, Math. Notes, 84:6 (2008), 879–882 | DOI | DOI | MR | Zbl

[18] B. S. Kashin, “Dyadic analogues of Hilbert matrices”, Russ. Math. Surv., 71:6 (2016), 1135–1136 | DOI | DOI | MR | Zbl

[19] B. S. Kashin, V. N. Temlyakov, “On a norm and approximate characteristics of classes of multivariable functions”, J. Math. Sci., 155:1 (2008), 57–80 | DOI | MR | Zbl

[20] Klivans A. R., Sherstov A. A., “Lower bounds for agnostic learning via approximate rank”, Comput. Complexity, 19:4 (2010), 581–604 | DOI | MR | Zbl

[21] E. D. Kulanin, “On the diameters of a class of functions of bounded variation in the space $L^q(0,1)$, $2\infty $”, Russ. Math. Surv., 38:5 (1983), 146–147 | DOI | MR | Zbl

[22] Lee T., Shraibman A., “An approximation algorithm for approximation rank”, Proc. 24th Annu. IEEE Conf. on Computational Complexity (Paris, 2009), IEEE, Los Alamitos, CA, 2009, 351–357 | MR

[23] Linial N., Mendelson S., Schechtman G., Shraibman A., “Complexity measures of sign matrices”, Combinatorica, 27:4 (2007), 439–463 | DOI | MR | Zbl

[24] Linial N., Shraibman A., “Lower bounds in communication complexity based on factorization norms”, Random Struct. Algorithms, 34:3 (2009), 368–394 | DOI | MR | Zbl

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

[26] Lorentz G. G., von Golitschek M., Makovoz Y., Constructive approximation: Advanced problems, Springer, Berlin, 1996 | MR | Zbl

[27] Talagrand M., Upper and lower bounds for stochastic processes: Modern methods and classical problems, Ergeb. Math. Grenzgeb. 3. Flg., 60, Springer, Berlin, 2014 | MR | Zbl

[28] Temlyakov V., Sparse approximation with bases, Birkhäuser, Basel, 2015 | MR | Zbl

[29] Temlyakov V., “Constructive sparse trigonometric approximation for functions with small mixed smoothness”, Constr. Approx., 45:3 (2017), 467–495 | DOI | MR | Zbl

[30] A. Zygmund, Trigonometric Series, v. 1, 2, Univ. Press, Cambridge, 1959 | MR | MR | Zbl