2
$\begingroup$

I want a collection of points $\{ x_1, \dots, x_m\}$ to sample a unit cube $[0,1]^n$ with $n >>1 $ in high dimensions so that summing over these points is approximate the integral over that space.

$$\frac{1}{m} \sum f(x_i) \approx \int_{[0,1]^n} f(x) \ dx $$

If I broke each segment $[0,1]$ into $10$ points, I would have to calculate $10^n$ values of my function $f$ - way too many.

Are there lattices I can use which become dense in $[0,1]^n$ as the mesh gets smaller, and whose points do not grow too quickly?

If I knew more about lattices, I could make this more precise.

$\endgroup$
1
  • 1
    $\begingroup$ Avoiding the exponential explosion here is commonly known as stratified sampling and you might have some luck searching under that term. $\endgroup$ Dec 31, 2013 at 19:05

2 Answers 2

5
$\begingroup$

This paper seems to directly address your question:

Art Owen. "Latin supercube sampling for very high-dimensional simulations." ACM Transactions on Modeling and Computer Simulation (TOMACS). Volume 8, Issue 1, Jan. 1998. (ACM link)

Here is its first sentence:


Owen1stSentence

The paper includes summaries of Latin hypercube sampling (LHS) and quasi-Monte Carlo (QMC) sampling; it cites about 50 references.

$\endgroup$
2
$\begingroup$

You face the curse of dimensionality. Besides the pretty old but simple and robust Monte Carlo integration and its relatives there are also methods based on sparse grids. For an overview see

E. Novak, "High dimensional integration", Advances in Computational Mathematics, volume 12, issue 1, 2000

or the slightly older

E Novak, K Ritter, "High dimensional integration of smooth functions over cubes", Numerische Mathematik, volume 75, issue 1, 1996.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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