@inproceedings{
hong2023fourierbased,
title={Fourier-Based Bounds for Wasserstein Distances and Their Implications in Computational Inversion},
author={Wanli Hong and Vladimir A Kobzar and Kui Ren},
booktitle={NeurIPS 2023 Workshop Optimal Transport and Machine Learning},
year={2023},
url={https://openreview.net/forum?id=1Yi0XQviNO}
}
Computational inverse problems entail fitting a mathematical model to data.  These problems are often solved numerically, by minimizing the mismatch between the model and the data using an appropriate metric. We focus on the case when this metric is the Wasserstein-$p$ ($W_p$) distance between probability measures as well as its generalizations by Piccoli et al.,  for unbalanced measures, including the Kantorovich-Rubinstein norm.  The recent work of Niles-Weed and Berthet established that $W_p$ is bounded from below and above by weighted $\ell_p$ norms of the wavelet coefficients of the mismatch, among other things, relying on the fluid dynamics formulation of $W_p$.   Building on this research,  we establish lower and upper bounds on $W_p$ on the hypercube and flat torus in terms of weighted $\ell_{q}$ norms of the Fourier coefficients of the mismatch. In this setting, for measures uniformly bounded above, the lower bound increases as $p$ increases. Based on that fact, in our setting, the lower bound resolves the open problem posed by Steinerberger to prove the existence  of a Fourier-based lower bound on $W_p$ that grows with $p$.  When $W_p$ is used as the mismatch metric in computational inversion, these bounds allow us to analyze the effects of stopping early the computational minimization of the mismatch on the resolution of frequencies, and the dependence of the resolution on $p$. Since the $W_p$ distance  is used in a broad range of other problems in mathematics and computational sciences, we expect that our bounds will also be of interest beyond inverse problems.
Fourier-Based Bounds for Wasserstein Distances and Their Implications in Computational Inversion
Wanli Hong Vladimir A Kobzar Kui Ren