Given $S = (X_1, \ldots, X_n)$, where each $X_i \in \mathbb{R}^2$, are there algorithms that produce $(X_{(1)}, \ldots, X_{(m)})$, where $m << n$ and the $X_{(i)}$ are sampled from $S$ to fill space (e.g. maximize distances)?

My problem arises from where the $X_i$ are iid bivariate normal, $n=10000$ and $m=100$. I want to sample an unknown noisy function that I'm trying to learn over the domain, so my goal is to sample it at a smaller number of representative locations of $S$.

I've found algorithms in the literature can fill in my domain with new points, but I want pre-existing ones.

So far I'm using a heuristic minimax style algorithm that samples from $S$, and then keeps points only if they are at least $d$ Euclidean distance from all other kept points, where $d$ is chosen by hand. This is sufficient for what I need, but I'm publishing results and I'd prefer use/cite something already established.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.