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

Question

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.

Answer 1

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)