Tractability of Multivariate Approximation over a Weighted Unanchored Sobolev Space

We study d-variate L (2)-approximation for a weighted unanchored Sobolev space having smoothness ma parts per thousand yen1. This space is equipped with an unusual norm which is, however, equivalent to the norm of the d-fold tensor product of the standard Sobolev space. One might hope that the problem should become easier as its smoothness increases. This is true for our problem if we are only concerned with asymptotic analysis: the nth minimal error is of order n (-(m-delta)) for any delta > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? It is easy to prove that no matter how the weights are chosen, the waiting period is at least m (d) , even if the error demand epsilon is arbitrarily close to 1. Hence, for ma parts per thousand yen2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So we will be unable to vanquish the curse of dimensionality unless m=1, i.e., unless the smoothness is minimal. In this paper, we prove the more difficult fact that our problem can be tractable if m=1. That is, we can find an epsilon-approximation using polynomially-many (in d and epsilon (-1)) information operations, even if only function values are permitted. When m=1, it is even possible for the problem to be strongly tractable, i.e., we can find an epsilon-approximation using polynomially-many (in epsilon (-1)) information operations, independently of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most omega variables, where omega is independent of d.