Solved – What does it mean that high dimensional integration is difficult

When we say numerical integration is difficult for high dimensional problems, what do we mean by high dimensional?

For example, in the Bayesian framework, the marginal normalizing constant can be hard to compute.

Does 'high dimensional' simply refer to the infinite integration range under which no closed form expression for the integral can be obtained?

What are the remedies in such cases and why? Are there any exceptions where closed form solution could be obtained?

To say an integration problem is high dimensional means that it has a large number of variables. In the ideal case, one can obtain a tractable, closed form expression for the integral. This will give the most accurate solution, and tends to be the most computationally efficient. But, such an expression often doesn't exist, so we have to resort to numerical integration.

In low dimensions, simple quadrature methods can be used. For example, one can evaluate the function on a fixed grid of points, then apply the trapezoid rule. But, the number of grid points needed grows exponentially with the number of variables. So, this method would require an infeasible amount of computation for more than a few variables. In higher dimensions, Monte Carlo integration is often used. Here, the function is evaluated at randomly chosen points, and different approaches are available for selecting the points.

When the problem involves integrating over a probability distribution, Markov chain Monte Carlo (MCMC) methods are popular. The idea here is to construct a Markov chain whose equilibrium distribution matches the probability distribution of interest, then sample points from this chain. Variational techniques are a popular alternative. This approach involves constructing an approximation to the distribution of interest, where the approximation has a simple, tractable form.

Similar Posts:

Rate this post

Leave a Comment