Sample multivariate PDF from KDE with different norm [closed]

Question

I am using KDE with a modified metric for the distance. The PDF is as expected (see below: color is the probability and the dot is the point used to fit the KDE). But due to the new metric, I cannot use the usual sampling methods as they suppose a gaussian kernel with $(||\textbf{x}-\textbf{x}_i||)$. Here I have like something like $1/(||\textbf{x}-\textbf{x}_i||)$. So, the new kernel would looks like:

$$K(\textbf{x}-\textbf{x}_i) = \exp\left(\frac{-1}{||\textbf{x}-\textbf{x}_i||*h}\right)$$

This kernel does not integrate to 1 so I bound it in the unit hypercube and I want to sample in this hypercube.

• How to generate new sample in this context?

From what I read (Find CDF from an estimated PDF (estimated by KDE), for instance), I have to come up with the multivariate inverse CDF.

• Is there a simple way to do this?

For now I just use a hack which consists in:

1. Sample the multivariate space and get PDF values
2. Then I use these two information with a uniform random generator to give me a sample.

It works but will get the curse of dimensionality. Something like this: https://stackoverflow.com/q/25642599

Even the CDF in a multivariate space would be enough I guess as I would be able to use some fixed point for example to do the inverse.

EDIT

Here is the result of this experiment. Color is the probability, black point is the point used for fitting the KDE and red points are samples generated using Metropolis-Hasting MCMC.

Answer 1

Rejection sampling!

Suppose you've got a distribution $P$ that you'd like to sample from, but can't, and a proposal distribution $Q$ that is kinda like $P$ which you can sample from. Then if you can find a number $M$ which bounds $p(x)/q(x)$, to sample from $Q$:

• Draw a sample $x$ from $P$
• Calculate a threshold $T =\frac{p(x)}{Mq(x)}$
• Draw a random number $t \sim U(0, 1)$.
• If $t \leq T$, return $x$
• Else go back to the beginning

You might have to bound the support of $P$ and $Q$ in order for $M$ to exist, and the speed of this whole process hinges on how close your proposal $Q$ is to $P$. In your case, a good proposal would be the uniform distribution over the unit cube.

If that isn't fast enough, the next places to look are at adaptive rejection sampling, Metropolis-Hastings MCMC, and then maybe an advanced MCMC scheme like NUTS.

Answer 2

UPDATED: If I understand your question correctly, you have generated a kernel density function from a set of data $x_1,...,x_n \in [0,1]^m$ using some non-standard kernel, and now that you have generated the "density", you want to be able to sample from this in a simple way. You are using a Gaussian kernel, but with an inverse substitution of the distance; your kernel function is:

$$K(x_i-x) \propto \exp \Bigg( -\frac{\lambda}{2 (x_i-x)^2} \Bigg) \quad \text{for all }x \in [0,1]^m.$$

---

Sampling from a KDE: For a set of data $x_1,...,x_n$ and a (un-normalised) kernel function $K$ the kernel density estimate (KDE) $\hat{p}$ is given by:

$$\hat{p}(x) \propto \frac{1}{n} \sum_{i=1}^n K(x_i-x).$$

(This might also have some other estimated parameters for the kernel, like a bandwidth, but that does not affect this question.) Since the KDE is literally just a uniform mixture distribution, using kernels placed at the data values, the simplest way to sample from this density is via the following two-step process:

• Step 1: Generate a random value $i \sim \text{U}\{1, ..., n\}$ representing a data point;

• Step 2: Now sample from the density with kernel $K$ centered at $x_i$. This can be done by a variety of methods, such as rejection sampling, Metropolis-Hastings, or transformation methods.

It is trivial to show that this gives you a random value from the density $\hat{p}$. This is because the latter is just a mixture distribution of the kernels, centered at the data points. This means that the problem of generating a random variable from a KDE degenerates down to the problem of generating a random variable from the chosen kernel. In you case, I would recommend using the present algorithm, with rejection sampling to sample from your kernel.

---