2023/06/23 by Stefan Heinrich, Heinrich, Stefan
Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Numerical Analysis (math.NA) #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2306.13499
openalex publication_date 2023/06/23 · openalex created_date 2023/06/27 · openalex updated_date 2026/07/28
We study the complexity of randomized computation of integrals depending on a parameter, with integrands from Sobolev spaces. That is, for r,d1,d2∈\mathbb N, 1≤ p,q≤ ∞, D1= [0,1]d1, and D2= [0,1]d2 we are given f∈ Wpr(D1× D2) and we seek to approximate Sf=∫D2f(s,t)dt (s∈ D1), with error measured in the Lq(D1)-norm. Our results extend previous work of Heinrich and Sindambiwe (J. Complexity, 15 (1999), 317--341) for p=q=∞ and Wiegand (Shaker Verlag, 2006) for 1≤ p=q<∞. Wiegand's analysis was carried out under the assumption that Wpr(D1× D2) is continuously embedded in C(D1× D2) (embedding condition). We also study the case that the embedding condition does not hold. For this purpose a new ingredient is developed -- a stochastic discretization technique. The paper is based on Part I, where vector valued mean computation -- the finite-dimensional counterpart of parametric integration -- was studied. In Part I a basic problem of Information-Based Complexity on the power of adaption for linear problems in the randomized setting was solved. Here a further aspect of this problem is settled.