Importance Sampling

The basic idea behind importance-sampled integration is to evaluate an estimate of a function’s expected value. This is done by generating random samples that follow the approximate probability density of the function begin integrated and using the result to estimate the integral.

Specifically, importance-sampled integration is based on the fact that an integral of arbitrary dimension, D, can be re-expressed as

\( \int_A f(a)da = \int_A f(a)\frac{p(a)}{p(a)}da = E\left\{\frac{f(a)}{p(a)}\right\} \)

where p(a) is the probability density function corresponding to the D-dimensional vector a and A is the D-dimensional space over which f(a) is integrated.

The former equation shows that we can easily solve the integral if we have knowledge of the weighted expected value of the function, E{f(a)/p(a)}. While it is difficult to evaluate the true expected value of an arbitrary function, we can estimate it by evaluating f(a)/p(a) for N random samples a_n following the probability density function,

\( E\left\{\frac{f(a)}{p(a)}\right\} \approx \frac{1}{N}\sum_{n=1}^{N}\frac{f(a_n)}{p(a_n)}. \)

The law of large numbers ensures that we will obtain the expected value in the limit,

\begin{eqnarray*} \lim_{N \to \infty}\frac{1}{N}\sum_{n=1}^{N}\frac{f(a_n)}{p(a_n)}=E\left\{\frac{f(a)}{p(a)}\right\}. \end{eqnarray*}

The key idea for importance sampling is that there is no requirement that p(a) have any particular form. In one dimension, and when the probability density function is uniform, the integral simplifies to

\begin{eqnarray*} \int_b^c f(a)da&=&(c-b)\cdot E\left\{f(a)\right\}, \end{eqnarray*}

which is the uniform/regular sampling case where the probability function is constant (with value 1/(c-b)).

We can improve upon the efficiency of the integral (i.e. the rate at which we converge to the true integral value) by having p(a) closely resemble f(a). In other words, if we place more samples where they matter most (where f(a) is greatest), we’ll get to the final result a lot faster. This is important when we’re integrating over an optical property like a reflectance or a scattering phase function where we know the relative importance of a particular sample (i.e. the magnitude of the optical property), but the evaluation of that sample is expensive (e.g. tracing a ray through the scene to collect the incident radiance).