12
$\begingroup$

Let $\vec{x} = (x_1, x_2, \dots, x_n) \in [0,1]^n$ and $f(\vec{x}): [0,1]^n \to \mathbb{C}$ be a function in these variables.

Is there a recursive scheme for this iterated integral?

$$\int_{[0,1]^n} \prod dx_i \;f(\vec{x}) $$

If $n = 10$ and I break $[0,1]$ into 100 segments, we have $10^{20}$ points to add up. There must be a smarter way.


In fact, the function I wish to integrate is the Haar measure of the Unitary group.

$$\int_{U(n)} f(A) \ dA = \frac{1}{n!} \int_{[0,2\pi]^n} \prod_{j<k} \big|e^{i \theta_j} - e^{i \theta_k}\big|^2 \cdot f(\theta_1, \ldots, \theta_n) \ \frac{d \theta_1}{2\pi} \ \cdots \ \frac{d \theta_n}{2\pi}$$

$\endgroup$
  • 2
    $\begingroup$ If your dimension is not too large, you may also consider sparse quadrature methods for your integral. $\endgroup$ – Paul Dec 31 '13 at 3:10
  • $\begingroup$ @Paul can you explain this topic more in an answer? I will probably up-vote $\endgroup$ – john mangual Dec 31 '13 at 3:11
15
$\begingroup$

For integrations with many variables, the Monte Carlo method usually is a decent fit. Its error decreases as $O (\sqrt{N})$ where N is the number of equidistributed points selected. Of course this is not good for low dimension (1D and 2D) spaces where high order methods exist. Most of these deterministic methods, however, take a large number of points in higher dimensions. For example, a 1st order 1D scheme is $O(\sqrt{N})$ in 2D and $O(N^{\frac{1}{4}})$ in 3D. The strength of the Monte Carlo method is that the error convergence is independent of space dimension. No matter whether your space is 1D or 100D, it is $O (\sqrt{N})$.

Since it is probabilistic, however, you need to integrate it multiple times using a set number of points to find a standard deviation and an estimate of your error.

$\endgroup$
  • 1
    $\begingroup$ For integration, the use of quasi-Monte-Carlo, for instance using Sobel sequences, is slightly better. $\endgroup$ – Dr. Lutz Lehmann Dec 30 '13 at 19:42
  • $\begingroup$ Ah, yes, I stated equi-distributed points (over pseudo-random) but didn't explicitly differentiate between the two. $\endgroup$ – Godric Seer Dec 30 '13 at 19:47
  • 1
    $\begingroup$ @GodricSeer Looks like Sobol sequences will build a nice evenly-spaced mesh, even in high dimensions. It seems he is addressing the same question: to have $$ \frac{1}{n} \sum f(x_i) \approx \int_{[0,1]^n} f \ dx $$ very quickly. Gray code and discrepancy seem to be issues. $\endgroup$ – john mangual Dec 30 '13 at 20:29
  • $\begingroup$ Yes, the Sobol sequency would build a good distribution of points. quasi-Monte-Carlo is likely one of the better methods for your problem. $\endgroup$ – Godric Seer Dec 30 '13 at 20:50
8
$\begingroup$

Sparse grid quadrature is an alternative approach to integrate in higher dimensions.

Quadrature relies on evaluating a weighted sum of function values at specific "optimal" points. Traditional quadrature uses a tensor product grid construction in higher dimensions, which means that you would have to evaluate the function at an exponentially growing number of points as the dimension increases.

The trick to sparse grid quadrature is that you can obtain the same order accuracy (in the asymptotic sense) using a small subset of the tensor product grid. The sparse points you choose end up being those that accurately integrate monomials of up to a desired total degree. The computational savings (compared to the tensor product grid) increase significantly as the dimension increases.

There are, however, drawbacks to this method that you should be aware.

  1. This method does not work well if your function is not smooth (or otherwise not well approximated by polynomial functions).
  2. While the order of accuracy of sparse grid quadrature may be equivalent to a tensor product grid, the relative accuracy may be much worse. This is because the constant in front of the sparse grid's order of accuracy can be very large.
  3. Sparse grids work well for relatively small dimensions. But there comes a dimension after which you'd probably be better off using another method (like monte carlo or its variants).

For more information on sparse grids, I recommend Burkardt's Sparse Grids in High Dimensions. If you're interested in code to generate sparse grids, you may want to consider these matlab files.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.