Physics approach to the variable-mass optimal-transport problem

Optimal transport (OT) has become a discipline by itself that offers solutions to a wide range of theoretical problems in probability and mathematics with applications in several applied fields such as imaging sciences, machine learning, and in data sciences in general. The traditional OT problem suffers from a severe limitation: its balance condition imposes that the two distributions to be compared be normalized and have the same total mass. However, it is important for many applications to be able to relax this constraint and allow for mass creation and/or destruction. This is true, for example, in all problems requiring partial matching. In this paper, we propose an approach to solving a generalized version of the OT problem, which we refer to as the discrete variable-mass optimal-transport (VMOT) problem, using techniques adapted from statistical physics. Our first contribution is to fully describe this formalism, including all the proofs of its main claims. In particular, we derive a strongly concave effective free-energy function that captures the constraints of the VMOT problem at a finite temperature. From its maximum we derive a weak distance (i.e., a divergence) between possibly unbalanced distribution functions. The temperature-dependent OT distance decreases monotonically to the standard variable-mass OT distance, providing a robust framework for temperature annealing. Our second contribution is to show that the implementation of this formalism has the same properties as the regularized OT algorithms in time complexity, making it a competitive approach to solving the VMOT problem. We illustrate applications of the framework to the problem of partial two- and three-dimensional shape-matching problems.

Automated summary

Optimal transport (OT) is a discipline offering solutions to various theoretical problems in probability and mathematics, with applications in imaging sciences, machine learning, and data sciences. The traditional OT problem has limitations, such as requiring normalized distributions with the same total mass. This paper introduces a generalized approach to OT, referred to as the discrete variable-mass optimal-transport (VMOT) problem, using techniques from statistical physics and proving its effectiveness by demonstrating its competitive time complexity and applications in shape-matching.