Wasserstein approximation schemes based on Voronoi partitions
This provides incremental improvements in measure approximation methods, relevant for applications in computer vision and machine learning where measures represent structured data like images.
The paper tackles the problem of approximating measures in Wasserstein space using Voronoi partitions, showing that structured approximations achieve an O(h) error rate for scaled lattices and O(N^{-1/d}) for N-term approximations, matching known optimal rates.
We consider structured approximation of measures in Wasserstein space $\mathrm{W}_p(\mathbb{R}^d)$ for $p\in[1,\infty)$ using general measure approximants compactly supported on Voronoi regions derived from a scaled Voronoi partition of $\mathbb{R}^d$. We show that if a full rank lattice $Λ$ is scaled by a factor of $h\in(0,1]$, then approximation of a measure based on the Voronoi partition of $hΛ$ 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. Additionally, we generalize our construction to nonuniform Voronoi partitions, highlighting the flexibility and robustness of our approach for various measure approximation scenarios. Finally, we extend these results to noncompactly supported measures with sufficient decay. Our findings are pertinent to applications in computer vision and machine learning where measures are used to represent structured data such as images.