N-Widths and ε-Dimensions for High-Dimensional Approximations

In this paper, we study linear trigonometric hyperbolic cross approximations, Kolmogorov n-widths d _n (W,H ^γ ), and ε-dimensions n _ε (W,H ^γ ) of periodic d-variate function classes W with anisotropic smoothness, where d may be large. We are interested in finding the accurate dependence of d _n (W,H ^γ ) and n _ε (W,H ^γ ) as a function of two variables n, d and ε, d, respectively. Recall that n, the dimension of the approximating subspace, is the main parameter in the study of convergence rates with respect to n going to infinity. However, the parameter d may seriously affect this rate when d is large. We construct linear approximations of functions from W by trigonometric polynomials with frequencies from hyperbolic crosses and prove upper bounds for the error measured in isotropic Sobolev spaces H ^γ . Furthermore, in order to show the optimality of the proposed approximation, we prove upper and lower bounds of the corresponding n-widths d _n (W,H ^γ ) and ε-dimensions n _ε (W,H ^γ ). Some of the received results imply that the curse of dimensionality can be broken in some relevant situations.