How to Cope With the Curse of Dimensionality?
Henryk Wozniakowski
Department of Computer Science
Columbia University
Institute of Applied Mathematics
University of Warsaw
Multivariate problems occur in many applications. They are defined on spaces of d-variate functions and d is often huge. Many multivariate problems suffer from the curse of dimensionality. This means that the minimal number of function values needed to compute an approximation to within ε is an exponential function of d.
In this talk we discuss how the curse of dimensionality can be vanquished by:
- switching to spaces with increasing smoothness of successive variables,
- switching to weighted spaces,
- switching to more lenient settings.