TL;DR
Standard Wasserstein distance struggles when comparing probability distributions that share the same shape but differ by a rigid spatial offset. This paper introduces Relative-Translation Invariant Wasserstein Distances ($RW_p$), proving they form valid metric spaces on translation quotient sets. For the quadratic case ($p=2$), optimal transport decouples into a Pythagorean sum of "bias" (mean difference) and "variance" (shape difference), yielding an efficient $RW_2$ Sinkhorn algorithm that avoids exponential numerical underflow and accelerates computation under large spatial shifts.
What Problem Does This Paper Address?
Optimal transport (OT) and Wasserstein distances are widely used across machine learning for domain adaptation, generative modeling, and tracking. However, classical Wasserstein distance $W_p$ measures both shape differences and absolute spatial displacement.
In domain adaptation, sensor recalibration, or meteorology (such as identifying similar storm geometries across a radar grid), practitioners frequently care about structural pattern similarity regardless of exact coordinate placement. If two identical convective storms appear 100 kilometers apart, standard $W_p$ yields a massive distance dominated purely by coordinate offset. Existing OT formulations lack an efficient, metric-preserving mechanism to evaluate distribution similarity under arbitrary translations.
Methods
-
Relative Translation Optimal Transport (ROT): The authors formulate an optimization problem seeking the minimal transport cost over all possible spatial shifts $s \in \mathbb{R}^n$: $$\text{ROT}(\mu, \nu, p) = \inf_{s \in \mathbb{R}^n} \min_{P \in \Pi(\mu, \nu)} \sum_{i,j} P_{ij} \|x_i - y_j + s\|_p^p$$ They prove that $RW_p = \text{ROT}^{1/p}$ is a true distance metric on the quotient space $\mathcal{P}_p(\mathbb{R}^n) / \sim$, where distributions that differ only by a translation belong to the same equivalence class.
-
Decoupling and Invariance for $p = 2$: Unlike general $p$ (which is non-convex in multi-dimensional spaces), the quadratic case ($p=2$) exhibits an exact structural decomposition:
-
The optimal translation is simply the difference in means: $s^* = \bar{\nu} - \bar{\mu}$.
- The optimal transport coupling $P^*$ is completely invariant to relative translations.
- Pythagorean Relationship: $W_2^2(\mu, \nu) = \|\bar{\mu} - \bar{\nu}\|_2^2 + RW_2^2(\mu, \nu)$, neatly partitioning distribution shift into "bias" and "variance."
-
$RW_2$ Sinkhorn Algorithm: Because shifting one distribution by $\bar{\nu} - \bar{\mu}$ preserves the optimal coupling while minimizing the maximum entry $\|C\|_\infty$ of the cost matrix, standard Sinkhorn iterations can be executed on centered supports. Standard $W_2$ can then be reconstructed via the Pythagorean identity without numerical instability.
-
General $RW_p$ Alternating Optimization: For $p \neq 2$, the authors prove a closed-form gradient for the outer objective, $\nabla_P F_p(P) = C(s_P)$, and provide an alternating gradient-descent / linear-programming scheme.
Datasets
- Synthetic Benchmarks:
- 1D and 10D standard normal distributions ($\mathcal{N}(0, I)$) tested with controlled translation shifts $s \in [0, 3]$.
- Discrete 1D distributions: Poisson ($\lambda = 1$), Geometric ($p = 0.5$), and Gamma ($\alpha = \beta = 2$) distributions.
- Real-World Meteorological Benchmark:
- Multi-Radar/Multi-Sensor (MRMS) quantitative precipitation estimation dataset centered on Dallas Fort Worth International Airport (DFW) from 2016 to 2022.
- Consists of 205,848 radar reflectivity images covering a $300 \times 300\text{ km}^2$ region, evaluated on static 2D snapshots and 3D spatio-temporal storm sequences.
Key Insights and Ideas
- Bias-Variance Interpretation of $W_2$: The decomposition $W_2^2 = \|\bar{\mu} - \bar{\nu}\|_2^2 + RW_2^2$ generalizes the Wasserstein-Bures metric beyond Gaussians to arbitrary distributions with finite second moments.
- Identical Couplings: Shifting distributions to align their means does not alter the underlying transport plan for $p=2$. You can compute classical $W_2$ by solving an easier, centered OT problem.
- Mitigating Sinkhorn Underflow: Sinkhorn uses the Gibbs kernel $K_{ij} = \exp(-C_{ij} / \lambda)$. Large spatial distances cause $C_{ij} \gg \lambda$, making $K_{ij}$ underflow to zero and triggering "division by zero." Pre-aligning centers keeps costs small, preserving numerical stability even when translations are large.
- Sub-Gaussian Complexity Guarantees: The authors prove that for high-dimensional sub-Gaussian distributions, pre-centering provably contracts $\|C\|_\infty$ with high probability, reducing Sinkhorn's $\mathcal{O}(m^2 \|C\|_\infty^3 \tau^{-3} \log m)$ complexity.
Key Results
- Error Explosion Avoidance: In 10D Gaussian numerical experiments ($N=1,000$, $\lambda=0.1$, $\epsilon=10^{-9}$), the classic Sinkhorn algorithm experienced complete numerical breakdown (computational error exploding from $\approx 0$ to $>100$) as translation length exceeded $2.0$. In contrast, the $RW_2$ Sinkhorn algorithm remained numerically stable with near-zero error across all tested shifts.
- Computational Speedup: Pre-centering distributions cut execution times significantly at larger translation magnitudes, avoiding stalled Sinkhorn iterations caused by extreme matrix scaling.
- Severe Weather Retrieval: When retrieving top-5 similar storm events from over 200,000 radar frames:
- Standard $W_2$ retrieved storms whose primary commonality was geographical proximity to the query center, regardless of geometry.
- $RW_2$ successfully retrieved storms with matching morphologies (e.g., squall lines, localized convective cores) irrespective of where they developed across the radar domain.
Limitations and Future Work
- Non-Convexity for General $p$: For $p \neq 2$, the outer objective is strictly non-convex in high dimensions. The proposed alternating algorithm only guarantees convergence to local stationary points, not global minima.
- Lack of Rotation Invariance: The formulation covers spatial translations only. The authors note that including rotations generally violates metric properties (e.g., triangle inequality). Full rigid-body ($SE(n)$) invariance remains an open challenge.
- Fixed Spatio-Temporal Hyperparameters: In sequence matching, spatial and temporal axes were combined using a fixed 1:1 weight rather than an adaptive, data-driven parameterization.
Summary updated