Skip to Main content Skip to Navigation
Journal articles

Optimal transport at finite temperature

Abstract : Optimal transport (OT) has become a discipline by itself that offers solutions to a wide range of theoretical problems in probability and mathematics. Despite its appealing theoretical properties, solving the OT problem involves the resolution of a linear program whose computational cost can quickly become prohibitive whenever the size of the problem exceeds a few hundred points. The recent introduction of entropy regularization, however, has led to the development of fast algorithms for solving an approximate OT problem. The successes of those algorithms have resulted in a popularization of the applications of OT in several applied fields such as imaging sciences and machine learning, and in data sciences in general. Problems remain, however, as to the numerical convergence of those regularized approximations towards the actual OT solution. In addition, the physical meaning of this regularization is unclear. In this paper, we propose an approach to solving the discrete OT 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 optimal transport problem at a finite temperature. Its maximum defines a pseudo distance between the two set of weighted points that are compared, which satisfies the triangular inequalities. The temperature dependent OT pseudo distance decreases monotonically to the standard 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 OT problem. We illustrate applications of the framework to the problem of protein fold recognition based on sequence information only.
Complete list of metadatas

https://hal-pasteur.archives-ouvertes.fr/pasteur-02348884
Contributor : Marie de Tarragon <>
Submitted on : Tuesday, November 5, 2019 - 2:42:56 PM
Last modification on : Monday, February 10, 2020 - 6:13:42 PM

Links full text

Identifiers

Citation

Patrice Koehl, Marc Delarue, Henri Orland. Optimal transport at finite temperature. Physical Review E , American Physical Society (APS), 2019, 100 (1), pp.013310. ⟨10.1103/PhysRevE.100.013310⟩. ⟨pasteur-02348884⟩

Share

Metrics

Record views

71