INTEGRATION AND APPROXIMATION OF MULTIVARIATE FUNCTIONS - AVERAGE-CASE COMPLEXITY WITH ISOTROPIC WIENER MEASURE

[摘要] We study the average case complexity of multivariate integration and L2 function approximation for the class F = C([0, 1]d) of continuous functions of d variables. The class F is endowed with the isotropic Wiener measure (Brownian motion in Levy's sense). For the integration problem, the average case complexity of solving the problem to within epsilon is proportional to epsilon-2/(1 + 1/d). This is a negative result since for a large number d of variables, the average case complexity is close to epsilon-2; the latter is also achieved by the classical Monte Carlo method in the randomized worst case setting. Furthermore, THETA(epsilon-2) is the highest possible average case complexity among ail probability measures with finite expectation of \\f\\L2(2). Thus, for large d, the average case complexity of the integration problem with isotropic Wiener measure behaves as the worst possible average complexity. For the function approximation problem, the complexity is even higher since it is proportional to epsilon-2d. These two negative results are in a sharp contrast to (H. Wozniakowski, Bull. Amer. Math. Soc. 24, No. 1 (1991), 185-194; Bull. Amer. Math. Soc., to appear), where, for F endowed with the Wiener sheet measure, small average case complexities have been proven. Indeed, they are of order epsilon-1(log epsilon-1)(d-1)/2 and epsilon-2(log epsilon-1)2(d-1) for the integration and function approximation problems, respectively. (C) 1994 Academic Press, Inc.

[发布日期] 1994-05-01