Before revision: We introduce kernel thinning, a simple algorithm for generating better-than-Monte-Carlo approximations to distributions \mathbb{P a suitable reproducing kernel k , and O(n^2) time, kernel thinning returns \sqrt{n in the associated reproducing kernel Hilbert space.
After revision: We introduce kernel thinning, a simple algorithm for generating better-than-Monte-Carlo approximations to distributions \mathbb{P a suitable reproducing kernel k , and O(n^2) time, kernel thinning compresses an n-point approximation to \mathbb{P in the associated reproducing kernel Hilbert space.