Journal
JOURNAL OF APPROXIMATION THEORY
Volume 158, Issue 1, Pages 97-125Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jat.2008.01.011
Keywords
Multivariate approximation; Standard information; Tractability; Worst case setting
Categories
Funding
- Australian Research Council Queen Elizabeth H Research Fellowship
- National Science Foundation [DMS-0609703, DMS-0608727]
- Humboldt Foundation
Ask authors/readers for more resources
We study multivariate approximation with the error measured in L-infinity and weighted L-2 norms. We consider the worst case setting for a general reproducing kernel Hilbert space of functions of d variables with a bounded or integrable kernel. Here d can be arbitrarily large. We analyze algorithms that use standard information consisting of n function values, and we are especially interested in the optimal order of convergence, i.e., in the maximal exponent b for which the worst case error of such an algorithm is of order n(-b). We prove that b epsilon [2P(2)/(2p + 1), p] for weighted L-2 approximation and b epsilon [2p(p - 1/2)/(2p + 1), p - 1/2] for L-infinity approximation, where p is the optimal order of convergence for weighted L-2 approximation among all algorithms that may use arbitrary linear functionals, as opposed to function values only. Under a mild assumption on the reproducing kernels we have p > 1/2. It was shown in our previous paper that the optimal order for Loo approximation and linear information is p - 1/2. We do not know if our bounds are sharp for standard information. We also study tractability of multivariate approximation, i.e., we analyze when the worst case error bounds depend at most polynomially on d and n(-1). We present necessary and sufficient conditions on tractability and illustrate our results for the weighted Korobov spaces with arbitrary smoothness and for the weighted Sobolev spaces with the Wiener sheet kernel. Tractability conditions for these spaces are given in terms of the weights defining these spaces. (C) 2008 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available