Journal
BIT NUMERICAL MATHEMATICS
Volume 49, Issue 3, Pages 543-564Publisher
SPRINGER
DOI: 10.1007/s10543-009-0232-1
Keywords
Weighted multivariate approximation; Randomized algorithms; Monte Carlo methods; Tractability
Funding
- Australian Research Council Queen Elizabeth II Fellowship
- National Sciences Foundation [DMS-0609703, DMS-0608727]
Ask authors/readers for more resources
We study approximation of multivariate functions from a general separable reproducing kernel Hilbert space in the randomized setting with the error measured in the L-infinity norm. We consider algorithms that use standard information consisting of function values or general linear information consisting of arbitrary linear functionals. The power of standard or linear information is defined as, roughly speaking, the optimal rate of convergence of algorithms using n function values or linear functionals. We prove under certain assumptions that the power of standard information in the randomized setting is at least equal to the power of linear information in the worst case setting, and that the powers of linear and standard information in the randomized setting differ at most by 1/2. These assumptions are satisfied for spaces with weighted Korobov and Wiener reproducing kernels. For the Wiener case, the parameters in these assumptions are prohibitively large, and therefore we also present less restrictive assumptions and obtain other bounds on the power of standard information. Finally, we study tractability, which means that we want to guarantee that the errors depend at most polynomially on the number of variables and tend to zero polynomially in n(-1) when n function values are used.
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