Wasserstein Distance

Paul Breiding, Kathlén Kohn, Bernd SturmfelsOberwolfach 2024 · DOI · OpenAlex

Abstract: A fundamental problem in metric algebraic geometry is distance minimization. This paper explores the computation of the Wasserstein distance from a data point to an algebraic variety, bridging polyhedral geometry and algebraic geometry to quantify the complexity of this optimization task.

Introduction

In the field of metric algebraic geometry, the core objective is often distance minimization: given a data point $\mathbf{u}$ and a variety $X$ defined by polynomial equations, one must find the point $\mathbf{x} \in X$ that is closest to $\mathbf{u}$. While Euclidean distance is the conventional metric, fields like statistics and machine learning frequently utilize the Wasserstein distance (or Earth Mover's Distance).

Unlike the smooth unit ball of the Euclidean norm, the Wasserstein distance is a polyhedral norm. This means its unit ball is a polytope, introducing non-smoothness that transforms the optimization problem into a piecewise-algebraic challenge requiring a combination of combinatorial search and polynomial system solving.

Methodological Framework

To address the non-smooth nature of Wasserstein distance, the authors decompose the problem into a finite set of smooth sub-problems. This approach is built upon three pillars:

  1. Combinatorial Stratification: The "face poset" of the unit ball polytope $B$ is used to categorize the problem. Each face $F$ of the polytope corresponds to a specific linear optimization problem over the variety.
  2. The Three-Step Algorithm:
    • Combinatorial Preprocessing: Identification of all faces of the Wasserstein unit ball (the root polytope).
  3. Numerical Optimization: Solving linear programs for each face to identify candidate optimal points.
  4. Algebraic Postprocessing: Utilizing Lagrange multipliers and elimination theory to determine the exact algebraic coordinates of the solution.
  5. Polar Degrees: The "algebraic degree"—the number of potential complex solutions—is quantified using polar degrees ($\delta_i$), allowing for a predictable measure of the problem's difficulty based on the variety's geometry.
The relationship between a polyhedral unit ball $B$ and its dual $B^*$, which is central to defining the Wasserstein distance as a polyhedral norm.

Quantifying Complexity

A primary insight of this research is the formula for the total number of critical points in the distance problem. It is expressed as a weighted sum linking the variety's algebraic complexity with the norm's combinatorial complexity:

$$\text{Total Critical Points} = \sum_{j=0}^{n-1} \delta_{n-j}(X) \cdot f_j(B)$$

Here, $\delta$ represents the polar degrees of the variety $X$, and $f_j(B)$ denotes the number of $j$-dimensional faces of the unit ball $B$. This formula demonstrates that the Wasserstein distance on a probability simplex is precisely the polyhedral norm whose unit ball is the "root polytope" $P_d^*$.

Empirical Findings and Statistical Models

The theoretical framework was tested against several landmark models in algebraic statistics, including 2-bit and 3-bit independence models and Segre-Veronese varieties. Key results include:

  • Exact Solutions: For the 2-bit independence model, the authors derived a complete piecewise-algebraic solution, showing that the 3D probability tetrahedron is divided into 12 distinct regions, each with its own distance formula.
  • Degree Drop: Experiments involving 1,000 uniform samples revealed that the actual number of solutions is often lower than the theoretical upper bound. This suggests that the specific orientation of Wasserstein balls relative to statistical models may simplify the mathematics in practical applications.
  • Polar Degree Reference: The work provides comprehensive tables for polar degrees of $k$-bit independence models. For instance, in a 7-bit model, while the variety's degree is 5,040, the dual variety (the hyperdeterminant) reaches a degree of 6,816.

Conclusion

By integrating polyhedral geometry with algebraic techniques, this framework provides a rigorous method for exact distance computation. While scalability remains a challenge due to the rapid growth of polytope faces in high dimensions, the use of polar degrees offers a powerful tool for predicting and managing the algebraic complexity of optimal transport problems in statistical contexts.

Summary updated

Abstract

Abstract A fundamental problem in metric algebraic geometry is distance minimization.
BibTeX
@inproceedings{breiding2024wasserstein,
  author = {Paul Breiding and Kathlén Kohn and Bernd Sturmfels},
  title = {{Wasserstein Distance}},
  booktitle = {Oberwolfach},
  year = {2024},
  doi = {10.1007/978-3-031-51462-3\_5},
}
Figure