A Variational Surface-Evolution Approach to Optimal Transport over Transitioning Compact Supports with Domain Constraints

Anthony YezziFluids 2024 · DOI

TL;DR

This paper introduces a novel variational approach to optimal mass transport (OMT) that simultaneously optimizes the mass distribution and its spatial-temporal support. By treating the support boundary as an evolving surface in space-time, the method can naturally incorporate complex constraints like obstacles or mandatory regions, offering a more flexible and powerful framework for OMT problems.

What Problem Does This Paper Address?

The classic optimal mass transport (OMT) problem aims to find the most efficient way to move mass from a source distribution to a target distribution. While powerful, existing methods, particularly those based on fluid dynamics (like Benamou-Brenier), often assume fixed or simple support domains for the densities. This becomes problematic when dealing with real-world scenarios where the regions of interest (supports) are complex, non-convex, and can change dynamically over time. Furthermore, incorporating constraints on where mass can or cannot go (obstacles, mandatory paths) is challenging with traditional OMT formulations. This paper addresses the need for an OMT framework that can handle transitioning, non-convex compact supports and arbitrary spatiotemporal constraints.

Methods

The authors extend the Benamou-Brenier fluid dynamical framework for OMT. The core innovation is to embed the problem in a higher-dimensional space-time (R$^{n+1}$) and treat the support boundary as a dynamic hypersurface. They introduce a space-time solenoidal vector field $W$ that encapsulates both mass density and momentum. The key is a joint variational formulation that optimizes both $W$ and its support $\Omega$ simultaneously. This is achieved by using a "shape gradient" of the space-time surface $\Gamma$ that outlines the support boundary $\partial\Omega$. This approach allows for the direct incorporation of spatiotemporal constraints, such as obstacles, by modifying the optimization problem on the evolving support. They also introduce a "density prior" to soften constraints and ensure the existence of solutions, which is crucial for shape optimization.

Datasets

Not discussed in the paper. The paper uses illustrative examples, including cardiac images and a toy problem with a disk and a hole, to demonstrate the method's capabilities.

Key Insights and Ideas

  • Joint Optimization of Mass and Support: The most significant insight is the simultaneous optimization of the mass distribution and its spatial-temporal support. This moves beyond traditional OMT where the support is often fixed or assumed to be simple.
  • Space-Time Hypersurface Representation: Representing the evolving support as a hypersurface in space-time ($\Omega \subset \mathbb{R}^{n+1}$) provides a unified geometric framework for handling dynamic boundaries and constraints.
  • Shape Gradient for Boundary Evolution: The introduction of a "shape gradient" allows for the direct evolution of the support boundary, enabling the method to adapt to complex geometries and constraints.
  • Density Prior for Well-Posedness: The use of a density prior (a convex penalty function) is crucial for ensuring the existence of solutions in the presence of complex support constraints, addressing a potential ill-posedness issue.
  • Flexibility for Constraints: The framework naturally accommodates various spatiotemporal constraints, including obstacles and mandatory regions, by modifying the optimization problem on the evolving support.

Key Results

The paper presents a theoretical framework and demonstrates its potential through illustrative examples.

  • Qualitative Demonstration: The method is shown to successfully interpolate between two non-convex cardiac image supports, preserving topological features.
  • Constraint Handling: A toy example demonstrates the ability to handle intermediate support constraints, such as evacuating mass from a hole within a disk, showing how mass redistributes to avoid obstacles.
  • Mathematical Framework: The paper derives the necessary variational formulations, optimality conditions, and gradient expressions for both the solenoidal field $W$ and the support boundary $\Gamma$.

Limitations and Future Work

  • Numerical Implementation: The authors acknowledge that while the mathematical formulation is complete, sophisticated numerical implementation strategies are still under investigation. The presented results are preliminary.
  • Existence of Solutions: The paper raises conjectures about the existence of solutions in the presence of intermediate support constraints, suggesting that further theoretical work is needed to rigorously prove existence under various constraint scenarios.
  • Soft vs. Hard Constraints: The paper explores using a "density prior" as a soft constraint to guide optimization, but future work could investigate the impact of hard constraints on density bounds.
  • Generalization: While the framework is presented for $\mathbb{R}^n$, future work could explore its application to more complex manifolds or specific application domains.

Summary updated

Abstract

We examine the optimal mass transport problem in Rn between densities with transitioning compact support by considering the geometry of a continuous interpolating support boundary Γ in space-time within which the mass density evolves according to the fluid dynamical framework of Benamou and Brenier. We treat the geometry of this space-time embedding in terms of points, vectors, and sets in Rn+1=R×Rn and blend the mass density and velocity as well into a space-time solenoidal vector field W|Ω→Rn+1 over a compact set Ω⊂Rn+1. We then formulate a joint optimization for W and its support using the shaped gradient of the space-time surface Γ outlining the support boundary ∂Ω. This easily accommodates spatiotemporal constraints, including obstacles or mandatory regions to visit.
BibTeX
@inproceedings{yezzi2024variational,
  author = {Anthony Yezzi},
  title = {{A Variational Surface-Evolution Approach to Optimal Transport over Transitioning Compact Supports with Domain Constraints}},
  booktitle = {Fluids},
  year = {2024},
  doi = {10.3390/fluids9050118},
}
Figure