Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Avoiding the exponential explosion here is commonly known as stratified sampling and you might have some luck searching under that term. –  Steven Stadnicki Dec 31 '13 at 19:05

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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