Abstract: 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 and its generalizations for unbalanced measures, including the Kantorovich-Rubinstein norm. 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. Steinerberger posed proving the existence of a Fourier-based lower bound on $W_p$ that grows with $p$, as an open problem. Building on this line work, we establish lower and upper bounds on $W_p$ in terms of, respectively, weighted $\ell_{p'}$ and $\ell_2$ norms of the Fourier coefficients of the mismatch where $p'$ is the Holder conjugate of $p$. Moreover, where the model and data have sufficient Sobolev regularity, the upper bound can be also expressed in terms of a weighted $\ell_{p'}$ norm. Our bounds holds for $p$ in $[1,2]$, and the lower bound resolves the above-mentioned open problem for such $p$. Moreover, in the context of computational inversion using $W_p$ as the mismatch metric, these bounds allow us to analyze the resolution of frequencies in the context of early stopping of the minimization process and beyond. Since this metric is used in a broad range of other problems in mathematics and computational sciences, we expect that our bounds will also be of interest independent from inverse problems.