Relative Translation Invariant Wasserstein Distance

Binshuai Wang, Qiwei Di, Ming Yin, Mengdi Wang, Quanquan Gu, Peng Wei

TL;DR

Standard Wasserstein distance can overemphasize global spatial shifts rather than intrinsic shape differences, while suffering from numerical instability when distributions are far apart. This paper introduces the Relative Translation Invariant Wasserstein Distance ($RW_p$), a new metric family that filters out global translations to focus purely on structural discrepancies. By leveraging this translation invariance, the authors develop algorithms that drastically reduce numerical errors and improve stability in optimal transport (OT) computations, demonstrating practical success in real-world thunderstorm pattern retrieval.

What Problem Does This Paper Address?

Optimal Transport (OT) and Wasserstein distances are foundational tools in machine learning for comparing probability distributions. However, they possess a major vulnerability: sensitivity to global translations and systematic perturbations. If two identical distributions are simply shifted in space, the standard Wasserstein distance reflects the distance of that spatial shift rather than their structural identity.

Furthermore, when distributions are far apart or have large coordinate values, standard OT algorithms (like linear programming solvers or the popular entropy-regularized Sinkhorn algorithm) suffer from severe numerical instability, such as floating-point underflow. The authors tackle a fundamental question: Can we design a metric and efficient algorithms that capture intrinsic distributional differences regardless of systematic translational shifts?

Methods

The authors introduce Relative Translation Optimal Transport (ROT), which minimizes transport cost by dynamically aligning one distribution with another via an outer optimization over a translation vector $t$. From this, they define the $RW_p$ distance and prove it is a valid metric on a quotient space.

To solve this problem, they propose two main algorithmic approaches:

  1. Bi-level Alternating Optimization (General $p \geq 1$): Because the joint optimization over the translation vector $t$ and the transport plan $P$ is non-convex in higher dimensions, the authors use a block-coordinate descent scheme. It alternates between fixing $t$ to solve for $P$ (using a warm-started dual simplex method to minimize compute) and fixing $P$ to update $t$ via gradient descent with Armijo backtracking.
  2. The Quadratic Special Case ($RW_2$-LP & $RW_2$-Sinkhorn): The authors prove a unique property for $p=2$: the optimal coupling matrix is completely invariant to relative translations, and the optimal translation vector is exactly the difference between the distributions' means. This allows them to "center" the distributions at their means before running standard LP or Sinkhorn solvers. This simple centering step dramatically improves numerical conditioning and eliminates kernel underflow without altering the final coupling matrix or the convergence rate.

Datasets

The paper evaluates the proposed algorithms using both synthetic benchmarks and a massive real-world dataset:

  • Synthetic Validation Sets: Used to evaluate numerical stability across varying dimensions ($d \in \{2, 10\}$) and translation magnitudes. These include Gaussian-to-Gaussian, Gaussian-to-Uniform, Gaussian-to-Geometric, and Gaussian-to-Poisson distribution pairs.
  • MRMS Thunderstorm Dataset: Real-world radar images from the Multi-Radar/Multi-Sensor System centered at Dallas Fort Worth International Airport (DFW). It contains 32,073 images (snapshots and sequences) spanning 2014 to 2022, thresholded at 35dBZ to create binary matrices representing storm patterns.

Key Insights and Ideas

  • The Magic of $p=2$: For the quadratic Wasserstein distance, centering the distributions by subtracting their means yields the mathematically exact optimal translation vector. This elegant decomposition does not hold true for other values of $p$ (like $p=1$), where finding the optimal translation remains non-convex.
  • Invariance Implies Stability: Because the optimal transport coupling matrix is invariant to translation when $p=2$, we can shift the distributions to a numerically friendly coordinate space (centered at the origin) to compute the distance safely, then analytically add back the translation component.
  • Centering Beats Scaling: Standard practice often relies on multiplicative normalization (scaling the cost matrix) to avoid numerical issues. The authors demonstrate that additive centering is often significantly more effective at preventing floating-point underflow.

Key Results

  • Numerical Error Reduction: In Gaussian-to-Uniform and Gaussian-to-Gaussian tasks with large translations, $RW_2$-Sinkhorn and $RW_2$-LP maintained consistently low numerical errors, whereas standard algorithms saw errors spike exponentially due to ill-conditioned matrices and underflow.
  • Thunderstorm Retrieval Performance: The $RW_p$ metrics excelled at finding morphologically similar storm patterns regardless of where they appeared on the radar map. When combined with a translation regularizer ($\lambda_m = 0.6$) to account for physical storm movement over time, $RW_1 + \lambda_m\text{mean}$ achieved the highest mean Average Precision (mAP) of 0.924, outperforming standard $W_2$ (0.897) and standard $\ell_2$ distance (0.693).
  • Computational Efficiency: The $RW_2$ algorithms achieved these stability gains with comparable or slightly lower running times than standard baselines, proving highly scalable.

Limitations and Future Work

  • Non-convexity for $p \neq 2$: For dimensions $d \geq 2$ and orders $p \neq 2$, the ROT optimization problem is inherently non-convex. This means the alternating optimization algorithm can potentially get trapped in local minima.
  • Weak Supervision Heuristic: The thunderstorm evaluation relies on a temporal consistency assumption (assuming storms close in time are structurally similar), which serves as a weak proxy and may not fully capture complex meteorological dynamics.
  • Future Directions: In a brief note on follow-up work, the authors mention that the $RW_2$ metric space admits a unique "cone geometry." This geometric perspective allows researchers to rigorously define relative Wasserstein angles and orthogonal projections, paving the way for more robust Gaussian approximations.

Summary updated

Abstract

Motivated by the Bures distance, we introduce a new family of distances, \emph{relative translation invariant Wasserstein distances}, denoted by $RW_p$, as an extension of the classical Wasserstein distances $W_p$ for $p \in [1, +\infty)$. We establish that $RW_p$ defines a valid metric and demonstrate that this type of metric is more intrinsic than the classical Wasserstein distance. A bi-level algorithm is designed to compute the general $RW_p$ distance between arbitrary discrete distributions. Moreover, when $p = 2$, we show that the optimal coupling matrix is invariant under distributional translation in the discrete setting, and we further propose two algorithms, the $\mathrm{RW}_2$-LP algorithm and the $\mathrm{RW}_2$-Sinkhorn algorithm, to improve the numerical stability of computing $W_2$ distance and the optimal coupling matrix solutions. Finally, we conduct three experiments to validate our theoretical results and algorithms. The first two experiments report that the $\mathrm{RW}_2$-LP algorithm and the $\mathrm{RW}_2$-Sinkhorn algorithm, both with and without normalization, can significantly reduce the numerical errors compared to standard algorithms. The third experiment shows that $RW_p$ algorithms are computationally scalable and applicable to the retrieval of similar thunderstorm patterns in practical applications.
BibTeX
@misc{wang2024relative,
  author = {Binshuai Wang and Qiwei Di and Ming Yin and Mengdi Wang and Quanquan Gu and Peng Wei},
  title = {{Relative Translation Invariant Wasserstein Distance}},
  year = {2024},
  eprint = {2409.02416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.02416},
}

Loading related content...

Figure