کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609016 | 1338400 | 2011 | 14 صفحه PDF | دانلود رایگان |
We consider approximation of weighted integrals of functions with infinitely many variables in the worst case deterministic and randomized settings. We assume that the integrands ff belong to a weighted quasi -reproducing kernel Hilbert space, where the weights have product form and satisfy γj=O(j−β)γj=O(j−β) for β>1β>1. The cost of computing f(x) depends on the number Act(x) of active coordinates in x and is equal to $(Act(x)), where $$ is a given cost function. We prove, in particular, that if the corresponding univariate problem admits algorithms with errors O(n−κ/2)O(n−κ/2), where nn is the number of function evaluations, then the ∞∞-variate problem is polynomially tractable with the tractability exponent bounded from above by max(2/κ,2/(β−1))max(2/κ,2/(β−1)) for all cost functions satisfying $(d)=O(ek⋅d), for any k≥0k≥0. This bound is sharp in the worst case setting if ββ and κκ are chosen as large as possible and $(d)$(d) is at least linear in dd. The problem is weakly tractable even for a larger class of cost functions including $(d)=O(eek⋅d). Moreover, our proofs are constructive.
Journal: Journal of Complexity - Volume 27, Issue 6, December 2011, Pages 505–518