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.

Multivariate PDF with new distance metric


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.

Sampling the KDE

  • 2
    $\begingroup$ duplicate (?) stats.stackexchange.com/questions/56700/… $\endgroup$ Jun 5, 2018 at 14:44
  • 2
    $\begingroup$ I'm unable to see how the duplicate doesn't answer your question. Regardless of how you develop the KDE, by definition it represents a distributional estimate as a mixture of components; and sampling from that mixture is performed as you would from any mixture. That's why I'm probing for a better understanding of the role played by this distance. $\endgroup$
    – whuber
    Jun 5, 2018 at 21:13
  • 2
    $\begingroup$ When you use a non-Gaussian kernel, you sample from that kernel, that's all. Conceptually the difference is trivial, although in practice some kernels are harder to sample from than others. $\endgroup$
    – whuber
    Jun 5, 2018 at 21:25
  • 4
    $\begingroup$ What exactly is your question? You seem to have an estimation already. Is the question now how to draw from this estimated pdf in principle? Or is this "just" a technical question on how to do this in code? In what shape/program/toolkit do you generate the pdf? The principle has been laid out very nicely by @whuber, especially in his last linked article. $\endgroup$
    – cherub
    Jun 11, 2018 at 14:17
  • 3
    $\begingroup$ Possible duplicate of Random sample using KDE or bootstrapping $\endgroup$
    – ironman
    Jun 16, 2018 at 14:05

2 Answers 2


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.

  • $\begingroup$ This is actually the first answer which does answer my questions! Will try this right away :) $\endgroup$
    – tupui
    Jun 14, 2018 at 10:42

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.

  • $\begingroup$ As I explained in the comments, I do not see how to "sample" from the Kernel in this context. Ok for exemple let say I have a Gaussian Kernel with the following metric: $\frac{1}{x_i - x}$ instead of $(x_i - x)$ and the multivariate distribution is totally unknown. $\endgroup$
    – tupui
    Jun 14, 2018 at 8:11
  • 2
    $\begingroup$ As I said in the answer, if you give full details of your kernel and explain how this is linked to your metric, I will try to make sense of this. With sporadic details spread across comments, I don't know what you're doing. $\endgroup$
    – Ben
    Jun 14, 2018 at 10:54
  • $\begingroup$ Well, the explanation is just above: Gaussian Kernel with an inverted distance measure. That is all. $\endgroup$
    – tupui
    Jun 14, 2018 at 13:01
  • 1
    $\begingroup$ Just wanted to say this answer is also perfect. I cannot accept 2 but gave a +1. Thx for the maths and details, it really helps. $\endgroup$
    – tupui
    Jun 19, 2018 at 17:32

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