1986 Reports

# Probabilistic setting of information-based complexity

We study the probabilistic (E, b)-complexity for linear problems equipped with Gaussian measures. The probabilistic (E, S)-complexity, comp@“˜(e, 6), is understood as the minimal cost required to compute approximations with error at most e on a set of measure at least 1 - 6. We find estimates of comp@(e, 6) in terms of eigenvalues of the correlation operator of the Gaussian measure over elements which we want to approximate. In particular, we study the approximation and integration problems. The approximation problem is studied for functions of d variables which are continuous after r times differentiation with respect to each variable. For the Wiener measure placed on rth derivatives, the probabilistic comp@(e, S) is estimated by ,((~/,)“(r+~)(ln(~/~))(d-“˜“r+““r‘+~‘), where a = 1 for the lower bound and a = 0.5 for the upper bound. The integration problem is studied for the same class of functions with d = 1. In this case, compPmb(e,6 ) = @((m/E)“@““˜).

## Subjects

## Files

- CUCS-237-86.pdf application/pdf 528 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-237-86
- Published Here
- November 2, 2011