Lattice Approximations in Wasserstein Space
Keaton Hamm Varun Khurana
We consider structured approximation of measures in Wasserstein space
$W_p(\mathbb{R}^d)$ for $p\in[1,\infty)$ by discrete and piecewise constant
measures based on a scaled Voronoi partition of $\mathbb{R}^d$. We show that if
a full rank lattice $\Lambda$ is scaled by a factor of $h\in(0,1]$, then
approximation of a measure based on the Voronoi partition of $h\Lambda$ is
$O(h)$ regardless of $d$ or $p$. We then use a covering argument to show that
$N$-term approximations of compactly supported measures is $O(N^{-\frac1d})$
which matches known rates for optimal quantizers and empirical measure
approximation in most instances. Finally, we extend these results to
noncompactly supported measures with sufficient decay.