Abstract
We consider structured approximation of measures in Wasserstein space$\mathrm{W}_p(\mathbb{R}^d)$ for $p\in[1,\infty)$ using general measureapproximants compactly supported on Voronoi regions derived from a scaledVoronoi 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 measurebased 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 ofcompactly supported measures is $O(N^{-\frac1d})$ which matches known rates foroptimal quantizers and empirical measure approximation in most instances.Additionally, we generalize our construction to nonuniform Voronoi partitions,highlighting the flexibility and robustness of our approach for various measureapproximation scenarios. Finally, we extend these results to noncompactlysupported measures with sufficient decay. Our findings are pertinent toapplications in computer vision and machine learning where measures are used torepresent structured data such as images.