N-widths and epsilon-dimensions for high-dimensional hyperbolic cross approximations

Abstract: 

In recent decades, there has been increasing interest in solving numerical problems that involve functions depending on a large number d of variables. These problems arise from many applications in mathematical finance, chemistry, physics, especially quantum mechanics, and meteorology. Classical methods suffer the "curse of dimensionality" coined by Bellmann. In fact, the computation time typically grows exponentially in d, and the problems become intractable already for mild dimensions d without further assumptions. A classical model, widely studied in literature, is to impose certain smoothness conditions on the function to be approximated; in particular, it is assumed that mixed derivatives are bounded. This is the typical situation for which "hyperbolic crosses" are made. Trigonometric polynomials with frequencies in hyperbolic crosses have been widely used for approximating functions with a bounded mixed derivative or difference. These classical trigonometric hyperbolic crosses date back to Babenko.

We suggest a new approach for the study of linear trigonometric hyperbolic cross approximations, namely Kolmogorov n-widths and epsilon-dimensions in isotropic Sobolev spaces of periodic d-variate function classes W with anisotropic smoothness, where d may be large. The n-width represents the error of the best approximation of W in a given Sobolev norm by linear subspaces of dimension at most n. Its inverse is  the minimal number n such that the approximation by a suitably chosen n-dimensional subspace yields the approximation error less than or equal to epsilon. We stress on finding the accurate dependence of the n-width on n and d, and of the epsilon-dimension on epsilon and d. The dimension n of the approximating subspace (the error accuracy epsilon) is the main parameter in the study of convergence rates with respect to n going to infinity (epsilon going to 0). 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 approximation error. Furthermore, in order to show the optimality of the proposed approximation, we prove upper and lower bounds of the corresponding n-widths and epsilon-dimensions. Some of the received results imply that the curse of dimensionality can be broken in some relevant situations. In other cases we are able to state negative results as a consequence of the obtained lower bounds.

This is a joint work with Tino Ullrich from the Hausdorff Center for Mathematics, Bonn, Germany.