Source-linked AI summary
Entropic and displacement interpolation: a computational approach using the Hilbert metric
Yongxin Chen, Tryphon T. Georgiou, Michele Pavon
TL;DR
Computing optimal mass transport effectively remains challenging. This paper uses Hilbert-metric contraction to find Schrödinger-system solutions and construct entropic interpolations. The discretized iteration converges linearly in the worst case, and entropic interpolation approximates displacement interpolation at sufficiently small diffusivity.
Problem
Effective computation of optimal mass transport remains challenging.
Source: §I · p. 2Method
The Schrödinger-system solution is obtained as the unique fixed point of a Hilbert-metric contraction, which yields an iterative computational scheme.
Source: §III · pp. 5, 9Results
The discretized iteration has linear worst-case convergence, and its fixed-point pair constructs entropic interpolation that approximates displacement interpolation at sufficiently small diffusivity.
Source: §IV · p. 11Takeaways & Limitations
The scheme provides a numerical approach to constructing entropic interpolations and approximating displacement interpolations.
Source: §IV · p. 11
Abstract
from arXiv · showhide
Monge-Kantorovich optimal mass transport (OMT) provides a blueprint for geometries in the space of positive densities -- it quantifies the cost of transporting a mass distribution into another. In particular, it provides natural options for interpolation of distributions (displacement interpolation) and for modeling flows. As such it has been the cornerstone of recent developments in physics, probability theory, image processing, time-series analysis, and several other fields. In spite of extensive work and theoretical developments, the computation of OMT for large scale problems has remained a challenging task. An alternative framework for interpolating distributions, rooted in statistical mechanics and large deviations, is that of Schroedinger bridges (entropic interpolation). This may be seen as a stochastic regularization of OMT and can be cast as the stochastic control problem of steering the probability density of the state-vector of a dynamical system between two marginals. In this approach, however, the actual computation of flows had hardly received any attention. In recent work on Schroedinger bridges for Markov chains and quantum evolutions, we noted that the solution can be efficiently obtained from the fixed-point of a map which is contractive in the Hilbert metric. Thus, the purpose of this paper is to show that a similar approach can be taken in the context of diffusion processes which i) leads to a new proof of a classical result on Schroedinger bridges and ii) provides an efficient computational scheme for both, Schroedinger bridges and OMT. We illustrate this new computational approach by obtaining interpolation of densities in representative examples such as interpolation of images.
I. INTRODUCTION
The introduction frames density interpolation as a problem for which linear interpolation has drawbacks, and connects optimal mass transport, Schrödinger bridges, and the Hilbert metric as geometric tools for interpolation.
I. INTRODUCTION
- Linear interpolation can produce fade-in/fade-out effects, motivating other approaches to density interpolation.The paper relates optimal mass transport, Schrödinger bridges, and the Hilbert metric as a geometric framework for interpolation.Source: §I · p. 1
II. BACKGROUND
- Effective computation of optimal mass transport remains challenging despite its geometric importance and broad applications.The introduction notes connections to gradient flows, the heat equation, and geodesic structures for interpolating densities.Source: §I · pp. 1–2
A. Optimal mass transport
- Monge’s formulation seeks a measurable map transporting equal-mass measures, but an optimal map may not exist in general.When the marginals are absolutely continuous, an optimal coupling is supported on the graph of a transport map.Source: A. Optimal mass transport · pp. 2–3
- When an optimal transport map exists, it defines displacement interpolation, a geodesic under the Wasserstein 2-metric.This interpolation connects the initial and final distributions.Source: A. Optimal mass transport · p. 3
B. Schr¨odinger bridges
- A Schrödinger bridge selects a path-space law matching the endpoint marginals that is closest in relative entropy to the Brownian prior; its one-time marginals form entropic interpolation.The Schrödinger system’s scaling pair is unique, and the bridge has specified one-time marginals.Source: B. Schr¨odinger bridges · pp. 3–4
C. The Hilbert metric
The Hilbert metric measures projective distance within the interior of a cone. Its contraction properties support using positive maps to construct solutions to equations.
C. The Hilbert metric
- The Hilbert metric is defined on the interior of a cone induced by a partial order on a Banach space.The definition uses order bounds between pairs of cone elements.Source: C. The Hilbert metric · p. 4
- The metric is projective because positive rescaling of either argument leaves the distance unchanged.It therefore measures distance between rays rather than individual elements.Source: C. The Hilbert metric · p. 4
- For positive linear maps, Birkhoff’s theorem bounds the contraction ratio and relates it to the map’s projective diameter.The paper uses contraction in this metric to ascertain and construct solutions to systems of equations.Source: C. The Hilbert metric · p. 5
D. Connections between the three topics
The paper links Schrödinger bridges to optimal mass transport through a vanishing-diffusion limit, then uses Hilbert-metric contraction to establish and compute solutions of the Schrödinger system.
D. Connections between the three topics
- As the reference Brownian motion’s diffusion coefficient tends to zero, the Schrödinger bridge and entropic interpolation converge weakly to the optimal coupling and displacement interpolation.Consequently, entropic interpolation with sufficiently small diffusion can approximate displacement interpolation.Source: D. Connections between the three topics · p. 5
- Because distributions are nonnegative and lie in a cone, the paper uses Hilbert geometry to connect the transport and Schrödinger bridge problems.The authors motivate this geometry through Birkhoff’s contraction result for linear endomorphisms of a positive cone.Source: D. Connections between the three topics · p. 5
III. SCHR ¨ODINGER SYSTEM REDUX
- The Schrödinger-system solution is a unique fixed point of a Hilbert-metric contraction, yielding a new existence-and-uniqueness proof and an efficient algorithm.The contraction has ratio less than one, and the limit is independent of the initial function.Source: §III · pp. 5, 7, 9
- For compact supports and an everywhere continuous, strictly positive kernel, the Schrödinger system has a solution unique up to reciprocal rescaling of its functions.The proof constructs the limit through iteration of the contraction.Source: §III · pp. 6, 8
- The contraction argument factors the map through positive bounded-function cones, whose non-empty interiors meet the Hilbert metric’s domain requirement.The authors note that L1_+ has empty interior and recast the composition so its factors map L∞_+ cones to themselves.Source: §III · p. 7
- Under those compact-support conditions, the paper also establishes a unique probability measure with the specified marginals and density q relative to a finite product measure.The stated conditions include absolute continuity of the endpoint probability measures.Source: §III · p. 10
- On R^n, absolutely continuous probability marginals and an everywhere continuous, strictly positive kernel likewise yield a unique probability measure and σ-finite product measure with the prescribed marginals and density q.The paper presents this as an extension to non-compact support.Source: §III · p. 10
IV. COMPUTATIONAL ALGORITHM
The algorithm restricts the endpoint densities to a compact support, discretizes the Schrödinger system, and iterates a contractive map to obtain an entropic interpolation. It also notes boundary and numerical-precision considerations that affect implementation.
IV. COMPUTATIONAL ALGORITHM
- A compact set S is chosen to contain at least 1−δ of each marginal’s mass, and the restricted densities are normalized before interpolation.The flow may spread beyond the endpoint supports, so S may need to be chosen conservatively to avoid excessive boundary constraints.Source: §IV · p. 11
- Discretizing the Schrödinger system yields vector operations whose contractive fixed-point iteration constructs the entropic interpolation with worst-case linear convergence.The displacement interpolation can then be approximated by entropic interpolation for sufficiently small diffusivity.Source: §IV · p. 11
- When noise intensity is too small, machine precision can cause numerical issues, which logarithmic coordinates are proposed to mediate.The approach stores and operates on logarithms of the kernel, marginals, and scaling vectors.Source: §IV · p. 11
V. NUMERICAL EXAMPLES
Three examples illustrate the algorithm: a one-dimensional Schrödinger bridge, its OMT counterpart with the same marginals, and image interpolation.
V. NUMERICAL EXAMPLES
- The one-dimensional Schrödinger bridge solution converges to the OMT solution as diffusivity goes to zero.The two problems use the same marginal distributions.Source: §V · p. 12
- A one-dimensional Schrödinger bridge problem is used to illustrate the algorithm.Source: §V · p. 12
- The final example illustrates interpolation between images using the algorithm.Source: §V · p. 12
A. One dimensional Schr¨odinger bridge
The example constructs Schrödinger bridges between two endpoint distributions of Brownian particles and examines how the interpolating flow changes with diffusivity. Larger diffusivity produces spreading followed by reassembly, with an apparent time symmetry.
A. One dimensional Schr¨odinger bridge
- The example seeks entropic interpolants between the particles’ distributions at t = 0 and t = 1 using a Brownian diffusion kernel.Source: A. One dimensional Schr¨odinger bridge · p. 12
- The interpolation flows are shown for diffusion coefficients √ϵ = 0.5, 0.2, 0.1, and 0.01.Source: A. One dimensional Schr¨odinger bridge · p. 12, Figure 2 · p. 13
- For larger diffusion coefficients, the density spreads from t = 0 before reassembling at t = 1, and its evolution appears time-symmetric.Source: A. One dimensional Schr¨odinger bridge · p. 12
B. One dimensional OMT
For the same marginals, the one-dimensional OMT example uses a deterministic-force setting and a closed-form optimal map. Its displacement interpolation is compared with entropic interpolation, which can suppress potentially spurious peaks.
B. One dimensional OMT
- The OMT example assumes deterministic forces and uses the closed-form optimal map for the one-dimensional problem.Source: B. One dimensional OMT · p. 13
- The exact optimal-map solution is used for the displacement interpolation and compared with entropic interpolation at √ϵ = 0.01.Source: B. One dimensional OMT · p. 13, Figure 3 · p. 14
- Small but non-negligible diffusion in the entropic interpolation suppresses potentially spurious peaks seen in the displacement interpolation.The passage makes this comparison between Fig. 3 and Fig. 2(c).Source: B. One dimensional OMT · p. 14, Figure 3 · p. 14
C. Image morphing
The section presents MRI brain-slice interpolation as an image-morphing example, treating normalized images as probability densities. Its computed interpolants use diffusivity ϵ = 0.01 and are shown at four intermediate times.
C. Image morphing
- The MRI example treats suitably normalized 2D images as probability densities and notes that interpolating slices may improve 3D reconstruction when scanning is limited.The stated application is MRI, where cost and time limit the number of scanned slices.Source: C. Image morphing · p. 14
- Figure 5 shows the two brain images chosen as interpolation endpoints.The data is identified as mri.dat in Matlab®.Source: C. Image morphing · p. 14, Figure 5 · p. 15
- Figure 6 shows algorithm-computed interpolants at t = 0.2, 0.4, 0.6, and 0.8 for a Schrödinger bridge with ϵ = 0.01.These are displacement interpolants based on solving the Schrödinger bridge problem.Source: C. Image morphing · p. 14, Figure 6 · p. 15
VI. CONCLUDING REMARKS
The conclusion contrasts linear interpolation’s drawbacks with OMT and Schrödinger-bridge interpolation, then identifies Hilbert-metric contraction as a route to solving the bridge system. The resulting fixed-point iteration converges linearly, while larger-scale applications are left to future numerical studies and software.
VI. CONCLUDING REMARKS
- Linear interpolation can produce bimodal Gaussian mixtures with shifting peak significance and requires infinite flow velocity when interpreted as particle-density interpolation.The paper characterizes these features as undesirable for image processing and physically unreasonable for particle flows.Source: §VI · p. 15
- Displacement interpolation requires an optimal transport map T, whose computation is challenging; quadratic-cost OMT is a zero-noise limit of stochastic control,,, [29],,.The stochastic-control problem steers a controlled diffusion between endpoint marginals with minimum energy.Source: §VI · p. 16
- Schrödinger-system solutions approximate displacement interpolation as stochastic excitation ϵ tends to zero [10], [13].The passage attributes this limit to Theorem (3).Source: §VI · p. 16
- The Hilbert metric makes a key map contractive, so its fixed points solve the Schrödinger bridge system with linear convergence.The authors expect further numerical studies and specialized software to support substantially larger-scale applications.Source: §VI · p. 16
VII. APPENDIX
The appendix establishes existence and uniqueness by constructing measures over compact exhaustions and passing to weak limits. The resulting coupling has the prescribed marginals, and the auxiliary product measure is uniquely determined.
VII. APPENDIX
- On each compact set Ck, the proof constructs a finite product measure νk and a measure πk, then extends them by zero outside Ck.The compact sets arise from the increasing sets Ak and Bk.Source: §VII · p. 16
- Restrictions of πk to a compact Cm are tight and uniformly bounded, so Prokhorov’s theorem yields weakly convergent subsequences.The bound given is πk(Cm) ≤ 1 − 1/(m + 1)^2.Source: §VII · pp. 16–17
- The limiting measure π is a probability measure whose marginals are µ0 and µ1.The proof obtains total mass one and weak convergence of the marginal sequences.Source: §VII · p. 17
- The proof constructs σ-finite ν from compatible restrictions on the compact exhaustion and establishes dν/dπ = 1/q, with ν a product measure.The restrictions satisfy dνm = dπ/q on Cm.Source: §VII · p. 17
- The uniqueness argument assumes an alternative product measure ν′ and probability measure π′ for which properties 1), 2), and 3) hold.Source: §VII · p. 17