Abstract
The Gromov-Wasserstein (GW) distances were proposed to compare distributions that do not lie in the same metric space, offering a powerful alternative to standard Wasserstein distances for probability measures on Euclidean spaces of different dimensions. This paper focuses on the $GW_2$ distance with a squared Euclidean ground cost and investigates the structure of the optimal transport plan between Gaussian distributions. We demonstrate that when the optimal plan is restricted to the set of Gaussian distributions, the problem yields a simple linear solution that aligns with the linear Gromov-Monge problem. Furthermore, we provide rigorous lower and upper bounds for the general Gromov-Wasserstein distance between Gaussians and propose that the Gaussian-restricted solution may indeed be the global optimum.
Introduction
In data science and machine learning, measuring the distance between probability distributions is a fundamental task. Standard Optimal Transport (OT), characterized by the Wasserstein distance, provides a geometrically intuitive framework for this. However, a significant limitation of standard OT is the requirement that the distributions must share the same ambient space (e.g., both must reside in $\mathbb{R}^d$).
When comparing datasets across different dimensions—such as matching a 2D image to a 3D model—the Gromov-Wasserstein distance becomes essential. Unlike standard OT, which compares point positions directly, GW compares the internal distances between points within each distribution. While the Wasserstein distance between two Gaussians has a well-known closed-form solution (the Bures-Wasserstein distance), the GW distance involves a non-convex quadratic optimization problem that is significantly more complex to solve and interpret.
The Gromov-Wasserstein Framework for Gaussians
The authors focus on the $GW_2$ distance using a squared Euclidean cost. The core of the research involves reformulating the GW problem into a sum of terms involving second-order and fourth-order co-moments. This decomposition reveals that the distance is fundamentally driven by the interaction between the variances and the kurtosis of the two distributions.
Gaussian Restriction and the Linear Solution
A key contribution of this work is the analysis of the problem when the transport plan is restricted to the class of Gaussian distributions. The authors prove (Theorem 4.1) that under this restriction, the optimal plan is an affine map. This simplifies the complex quadratic optimization into a linear problem, which the authors term the "linear Gromov-Monge problem."
The PCA Connection: Aligning the Axes
The geometric intuition behind this linear solution is striking: the optimal Gaussian transport map essentially performs a form of Principal Component Analysis (PCA) on both distributions. It aligns the principal components (the axes of the ellipsoidal distributions) in order of their importance, as determined by their eigenvalues. For example, if mapping a 3D distribution to a 2D one, the map aligns the longest axis of the 3D ellipsoid with the longest axis of the 2D ellipse. This alignment ensures that the internal structure of the data is preserved as much as possible during the transformation.
Theoretical Bounds
Because proving that the Gaussian plan is the global optimum for all possible plans is mathematically challenging, the authors establish two critical bounds:
- Lower Bound (LGW): Derived by optimizing the interaction terms separately, providing a theoretical floor for the distance.
- Upper Bound (GGW): Defined by the value of the distance achieved by the optimal Gaussian-restricted plan.
They demonstrate that these bounds are remarkably tight. Specifically, the gap between the lower and upper bounds is controlled by the Frobenius norms of the covariance matrices. When the distributions share similar "shapes" (i.e., similar ratios between their eigenvalues), the bounds converge, and in the specific case where one distribution is a rescaled version of the other, the Gaussian plan is proven to be the global optimum.
Empirical Validation and Conjecture
To complement the theoretical derivations, the authors conducted numerical experiments using synthetic Gaussian distributions in varying dimensions. Utilizing the Python Optimal Transport (POT) library, they compared empirical numerical solutions to their theoretical GGW formula.
The results show that as the number of samples increases, the empirical GW solution converges consistently to the derived Gaussian map. This empirical evidence leads to a bold conjecture: the Gaussian plan is likely the global optimal plan between two Gaussian distributions, even when non-Gaussian plans are permitted.
Conclusion
This research provides a significant step toward a closed-form understanding of the Gromov-Wasserstein distance. By identifying the linear nature of the optimal Gaussian plan and its connection to PCA, the authors provide both a computational shortcut (the GGW formula) and a clear geometric intuition for cross-dimensional alignment. While the general proof of the Gaussian optimality conjecture remains an open problem, this work provides the theoretical foundation and "ground truth" necessary for future explorations into more complex structures, such as Gaussian mixture models and non-Euclidean cost functions.
Summary updated