Gromov-Wasserstein distances between Gaussian distributions

Julie Delon, Agnès Desolneux, Antoine Salmona

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:

  1. Lower Bound (LGW): Derived by optimizing the interaction terms separately, providing a theoretical floor for the distance.
  2. 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

Abstract

Gromov–Wasserstein distances were proposed a few years ago to compare distributions which do not lie in the same space. In particular, they offer an interesting alternative to the Wasserstein distances for comparing probability measures living on Euclidean spaces of different dimensions. We focus on the Gromov–Wasserstein distance with a ground cost defined as the squared Euclidean distance, and we study the form of the optimal plan between Gaussian distributions. We show that when the optimal plan is restricted to Gaussian distributions, the problem has a very simple linear solution, which is also a solution of the linear Gromov–Monge problem. We also study the problem without restriction on the optimal plan, and provide lower and upper bounds for the value of the Gromov–Wasserstein distance between Gaussian distributions.
BibTeX
@article{delon2022gromov,
  author = {Julie Delon and Agnès Desolneux and Antoine Salmona},
  title = {{Gromov-Wasserstein distances between Gaussian distributions}},
  journal = {J. Appl. Probab.},
  year = {2022},
  doi = {10.1017/jpr.2022.16},
}
Figure