# dense lattices in high dimensions

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.

-
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

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:

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

-

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.

-