# Resampling points in R^n so that kernel density is roughly uniform

Let's say we have points $x_1,\ldots,x_n\in\mathbb{R}^N$ and let $X=\{x_1,\ldots,x_n\}$. I wish to produce a resampling $y_1,\ldots, y_m\in X$ (allowing repetitions) such that the new kernel density estimates at $y_i$ are all roughly equal. That is, I want my resampling to obey $$q_i = \frac{1}{m}\sum_{k=1}^m K(y_i-y_k) \approx \frac{1}{m}\sum_{k=1}^m K(y_j-y_k) = q_j$$ for all $i$ and $j$. A solution for the case of the Gaussian kernel would be sufficient, though a general solution would of course be very appealing as well.

Motivation: The hope would be that if I'm given a decently sampled manifold (though not necessarily uniformly sampled) I could through this method, arrive at an approximate uniform sampling. Or at least less biased one. For example, a naive sampling of the sphere may yield points accumulated at the poles, but then after resampling as above, one would hope to get a uniform sampling.

• Could you explain what such a subsample would accomplish? What's its purpose?
– whuber
May 28, 2017 at 14:44
• The main purpose would be to take a non uniform sampling of a manifold and produce a uniform sampling in nice cases. May 28, 2017 at 23:58
• Yes, yes: you already said that. But what would be the purpose of that uniform sample? What's the point? What would you do with it that you couldn't do (even better) with the original sample? (After all, this subsampling procedure loses information.)
– whuber
May 29, 2017 at 13:45
• I don't think there needs to be a reason beyond mere curiosity. But if a reason helps, there are various unsupervised learning algorithms that work better when the sampling of the manifold is uniform. Since the information of interest is the shape and not the distribution itself, it may sometimes be beneficial to work with an alternative distribution. If one does not have access to the data generating process one option would be to resample. Dec 14, 2018 at 23:27

Your conditions require resampling $$x_i$$ with probability inversely proportional to the original density estimates at $$x_i.$$ This is obvious: only such weights will produce new density estimates that have a constant value at each data point.

Here is an example. The data are shown in the rug plot at the bottom; the original kernel density estimate (KDE) is plotted in gray; the mean KDE of the resamples (of the same size as the original sample) is plotted in black. It uses the same bandwidth as the original KDE. Where your data are close to each other, the resampling produces a near-constant density (that is, the required uniform distribution). Where data are far apart and beyond their support there's little you can do: everything depends on the kernel bandwidth at those locations.

These results don't depend on the dimensionality of the data.

The R code to produce this example follows.

#
# Create a dataset.
#
set.seed(17)
x <- rnorm(80)
#
# Compute the initial density estimate.
#
x.kde <- density(x)
f.hat <- splinefun(x.kde$$x, x.kde$$y)
#
# Compute the resampling weights.
#
p <- 1 / f.hat(x)
p <- p / sum(p)

# Plot the original density estimate:
curve(f.hat(x), min(x), max(x), col="Gray", lwd=2, xaxt="n",yaxt="n",bty="n")
rug(x)
mtext("x", side=1, line=0)
mtext("Density", side=2, line=0)

# Plot the reweighted estimate. This is the expectation of the KDE with
# weighted sampling from x with weights p:
lines(density(x, bw=x.kde\$bw, weight=p), lwd=2)