# Multivariate numerical integration with a non-uniform grid

I want to approximate the integral:

$$I = \int f(\boldsymbol{x})d\boldsymbol{x}$$

where $\boldsymbol{x}$ is $d$-dimensional. I have a set of non-equally spaced points $\boldsymbol{x}_1, \dots, \boldsymbol{x_n}$, and the corresponding values $f(\boldsymbol{x}_1), \dots, f(\boldsymbol{x_n}$), and I would like to use them to approximate the integral $I$. Actually the integral is over $R^d$, but I know that $f(\boldsymbol{x})$ goes to zero quite rapidly outside my sample $\boldsymbol{x}_1, \dots, \boldsymbol{x_n}$.

My question is the following: are there rules to approximate the integral using the non-equally spaced points? I've found simple rules for the univariate case, but for multiple dimensions. Thanks

Note: the points $\boldsymbol{x}_1, \dots, \boldsymbol{x_n}$ are given and I can't choose them.

• What dimension is your integral (line, surface, volume), and what the bounds? – meawoppl Jun 17 '13 at 18:27
• I have between 3 and 7 dimensions, depending on the problem. The integral is over $R^d$, but the sample covers most of the mass, so I could assumes that the area outside the sample doesn't contribute to the integral. – Jugurtha Jun 18 '13 at 8:43
• I might be tempted to try doing some form of Kernel Density Estimate to get your sampling to act uniform, then move forward from there. – meawoppl Jun 22 '13 at 21:37
• I guess the problem with KDE is that the quality of the estimates degrade very rapidly as $d$ increases. – Jugurtha Jun 22 '13 at 23:30
• What is your total point count? – meawoppl Jun 23 '13 at 17:49

## 1 Answer

This depends on how many dimensions you have an how many points. Also on how the points are structured.

If the number of dimensions are high and the points are randomly chosen, you essentially have a Monte Carlo integration procedure. If the points are randomly chosen from a distribution, then you have a kind of importance sampling.

If the number of points is small and you are in a low-dimensional situation, then you can think of this as trying to find a polynomial that interpolates $f(x)$ and the weights are then computed so that the integral over $f(x)$ is chosen as the integral over the approximating polynomial.