Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
In this note, we prove that the following function space with absolutely convergent Fourier series F_d:={ f∈ L^2([0,1)^d) | f:=∑_k∈ℤ^d|f̂(k)|max(1,log|k|_∞)<∞} with f̂(k) being the k-th Fourier coefficient of f and |k|_∞:=max_j|k_j| is polynomially tractable for multivariate integration in the worst-case setting. Here polynomial tractability means that the minimum number of function evaluations required to make the worst-case error less than or equal to a tolerance ε grows only polynomially with respect to ε^-1 and d. It is important to remark that the function space F_d is unweighted, that is, all variables contribute equally to the norm of functions. Our tractability result is in contrast to those for most of the unweighted integration problems studied in the literature, in which polynomial tractability does not hold and a weaker notion of tractability is necessary. Our proof is constructive in the sense that we provide an explicit quasi-Monte Carlo rule that attains a desired worst-case error bound.
READ FULL TEXT