New averaging technique for approximating weighted integrals (Q1023278)

The authors consider the problem of approximating weighted integrals \[ I_{\rho}(f)=\int_D f(x) \rho(x) \,dx, \] where \(D \subset \mathbb{R}^d,\) \(\rho\) is a given probability density function, and \(f \in H(K)\) where \(K\) is the kernel of the reproducing kernel Hilbert space \(H(K)\). Standard averaging techniques require \(\int_DK(x,x)\rho(x)\,dx < \infty\); the authors discuss a new technique that requires only \(\int_D\sqrt{K(x,x)}\rho(x)\,dx < \infty\). As a consequence, there exist algorithms with worst case errors bounded by \(O(n^{-0.5})\) where \(n\) is the number of points in which \(f\) is evaluated, for a wider class of problems than known so far. The authors also obtain a new class of randomized algorithms with errors bounded by \(O(n^{-1}\sqrt{\ln(\ln(n))}).\)