Schrodinger Bridges on Discrete Domains
ISEF · 2022 Mathematics Third Award
Overview
Dynamical optimal transport is a field in mathematics and computer science involving interpolation between two probability measures. While dynamical optimal transport on continuous domains is well-understood, algorithms for solving the problem numerically struggle with both accuracy and efficiency. We apply existing theory surrounding Schrödinger bridges to arrive at a system of discrete dual variables which approximate the solutions to the dynamical optimal transport problem. We then propose a novel application of Sinkhorn's algorithm which can be used to numerically solve the dynamical optimal transport problem on discrete surfaces. We show empirically that this algorithm exhibits state-of-the-art performance on interpolation of probability measures defined on triangular meshes. We then propose an entropy-regularized variation of the semi-discrete optimal transport problem, in analogy to continuous Schrödinger bridges posed by Lavenant et al. and prove a result regarding the form of its solution.
Awards (3)
- Third Award of $1,000 $1,000
- American Mathematical Society: Third Award of $500 $500
- National Security Agency Research Directorate : Second Place Award “Mathematics”
Competition history
- ISEF 2022
Resources
Related projects
CWSF · 2026
A Novel Approach to Sinkhorn ε-Annealing: A 3.62x Speedup for the Optimal Transport Problem
ISEF · 2024
Finding Numerical Solutions to Partial Differential Equations With Deep Learning
ISEF · 2019
An Optimized Multigrid Algorithm for Enabling Efficient Physical Simulations on Realistic Geometries
ISEF · 2020
Optiming Length of Planar Curves
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair