Curse of dimension
curse of dimensionality
Many high-dimensional problems are difficult to solve for any numerical method (algorithm). Their complexity, i.e., the cost of an optimal algorithm, increases exponentially with the dimension. This is proved by providing exponentially large lower bounds that hold for all algorithms. Many problems suffer from the curse of dimension. Examples include numerical integration, optimal recovery (approximation) of functions, global optimization, and solution of integral equations and partial differential equations. It does not, however, hold for convex optimization and ordinary differential equations. The term "curse of dimensionality" seems to go back to R. Bellman [a2].
The investigation of the curse of dimension is one of the main fields of information-based complexity, see also Optimization of computational algorithms. Whether a problem suffers from the curse of dimension depends on the exact definition of the norms and function classes that are studied. Some high-dimensional problems can be computed efficiently using the Smolyak algorithm.
The curse of dimension typically happens in the worst-case setting, where the error and cost of algorithms are defined by their worst performance. One can hope to break the curse of dimension by weakening the worst-case assurance and switching to the randomized setting (see also Monte-Carlo method) or to the average-case setting (see Bayesian numerical analysis).
Below, results for numerical integration are discussed in more detail. Many of the results are similar for other problems such as approximation (optimal recovery) of functions, solution of partial differential equations and integral equations.
Consider a quadrature formula of the form
with and for the approximation of the integral
Let be a class of integrable functions on . Below, will be the unit ball in a suitable Banach space. The (worst case) error of on is defined by
and one also defines
The number is the (worst case) error of the optimal cubature formula (for the class ) when at most sample points are used. It is known that formulas of the form (a1) are general enough. Indeed, non-linear methods and adaptive quadrature do not yield better estimates if is convex and symmetric. Hence, one may say that the -complexity of the problem is given by the number
Much is known concerning the order of and of related numbers (such as widths and -entropy (see also Width; -entropy; or [a9]), for many different ). Classical results on the order, see (a2) and (a3) below, contain unknown constants that depend on and therefore cannot always answer the question whether there is a curse of dimension or not.
Two specific results on the order of are as follows. Let be the classical space with norm
where and , and let be the unit ball of . It is known [a1] that
Hence, integration for the class suffers from the curse of dimension. Define now a tensor product norm by
for , where the sum is over all with for all . This is the space of functions with bounded mixed derivatives. Let be the respective unit ball. It is known [a8] that
This result of course implies an upper bound
for all , hence the order of convergence does not depend on . Nevertheless, this problem suffers from the curse of dimension, see [a13].
The lack of the curse of dimension is related to the notion of tractability for continuous problems which was studied by H. Woźniakowski and others, see [a6], [a7], [a11], [a12]. The problem is tractable (in and ) if
for some positive constants , and .
There are general results characterizing which problems are tractable. In particular, this holds for weighted tensor product norms, see [a7], [a13], under natural conditions on weights. The weighted norms correspond to the common fact that for high-dimensional problems usually some variables are "more important" than others. The classical discrepancy also corresponds to a space of functions with bounded mixed derivatives, see [a4]. The respective integration problem is tractable, with upper bounds of the form , see [a13].
In the randomized setting one considers quadrature formulas (a1) where the sample points and the coefficients are random variables. The error of a randomized method can be defined by
where stands for mathematical expectation, and one also considers the minimal randomized error , see [a1], [a3], [a5], [a10], [a12], where more general notions are discussed. Instead of (a2), one now has
The classical Monte-Carlo method gives an upper bound for all these spaces, without an additional constant. Hence the problem is tractable in the randomized setting. Many other problems which are intractable in the worst-case setting stay intractable in the randomized or average-case setting.
For results concerning the average-case setting see Bayesian numerical analysis.
|[a1]||N.S. Bakhvalov, "On approximate computation of integrals" Vestnik MGU Ser. Math. Mech. Astron. Phys. Chem. , 4 (1959) pp. 3–18 (In Russian)|
|[a2]||R. Bellman, "Dynamic programming" , Princeton Univ. Press (1957)|
|[a3]||S. Heinrich, "Random approximation in numerical analysis" K.D. Bierstedt (ed.) et al. (ed.) , Proc. Funct. Anal. Conf. Essen 1991 , Lecture Notes Pure Appl. Math. , 150 , M. Dekker (1993) pp. 123–171|
|[a4]||H. Niederreiter, "Random number generation and quasi-Monte Carlo methods" , SIAM (Soc. Industrial Applied Math.) (1992)|
|[a5]||E. Novak, "Deterministic and stochastic error bounds in numerical analysis" , Lecture Notes Math. , 1349 , Springer (1988)|
|[a6]||E. Novak, I.H. Sloan, H. Woźniakowski, "Tractability of tensor product linear operators" J. Complexity , 13 (1997) pp. 387–418|
|[a7]||I.H. Sloan, H. Woźniakowski, "When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?" J. Complexity , 14 (1998) pp. 1–33|
|[a8]||V.N. Temlyakov, "Approximation of periodic functions" , Nova Science (1994)|
|[a9]||V.M. Tikhomirov, "Approximation theory" , Encycl. Math. Sci. , 14 , Springer (1990)|
|[a10]||J.F. Traub, G.W. Wasilkowski, H. Woźniakowski, "Information-based complexity" , Acad. Press (1988)|
|[a11]||G.W. Wasilkowski, H. Woźniakowski, "Explicit cost bounds of algorithms for multivariate tensor product problems" J. Complexity , 11 (1995) pp. 1–56|
|[a12]||H. Woźniakowski, "Tractability and strong tractability of linear multivariate problems" J. Complexity , 10 (1994) pp. 96–128|
|[a13]||E. Novak, H. Woźniakowski, "When are integration and discrepancy tractable" (in preparation)|
Curse of dimension. Erich Novak (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Curse_of_dimension&oldid=14053