Fast and Smooth Interpolation on Wasserstein Space

Sinho Chewi, Julien Clancy, Thibaut Le Gouic, Philippe Rigollet, George Stepaniants, Austin Stromme

Abstract

We propose a new method for smoothly interpolating probability measures using the geometry of optimal transport. To that end, we reduce this problem to the classical Euclidean setting, allowing us to directly leverage the extensive toolbox of spline interpolation. Unlike previous approaches to measure-valued splines, our interpolated curves (i) have a clear interpretation as governing particle flows, which is natural for applications, and (ii) come with the first approximation guarantees on Wasserstein space. Finally, we demonstrate the broad applicability of our interpolation methodology by fitting surfaces of measures using thin-plate splines.

Introduction

In fields like single-cell genomics and climate science, researchers often observe populations—represented as probability measures—at discrete time intervals. To understand the underlying processes, it is necessary to "fill in the gaps" by interpolating between these measures to reconstruct smooth trajectories. Standard Euclidean interpolation fails in this context because it does not respect the geometry of distributions; for instance, linearly interpolating between two displaced peaks results in the first peak fading out while the second fades in, rather than a single peak moving across the space.

While Wasserstein space (the geometry of optimal transport) provides a natural framework for this, existing solutions like P-splines and E-splines are either computationally prohibitive or fail to provide deterministic "Monge" trajectories. This means a single starting point might split into multiple paths, which is physically unrealistic for many biological and physical applications.

Transport Splines: A Two-Step Approach

The authors propose a two-step "Transport Spline" algorithm that decouples the geometry of the space from the interpolation logic:

  1. Coupling: The method uses Monge maps (optimal transport maps) to link observed measures. Given measures at times $t_0, t_1, \dots, t_N$, it computes the map from $t_0$ to $t_1$, $t_1$ to $t_2$, and so on. This creates a sequence of points in $\mathbb{R}^d$ for every "particle" in the initial distribution.
  2. Euclidean Interpolation: Standard Euclidean cubic splines are then applied to these sequences of points.

This approach is "trajectory-aware." Because the second step uses a standard Euclidean backend, the method is highly flexible. For example, cubic splines can be swapped for thin-plate splines to interpolate measures indexed by 2D spatial coordinates, such as temperature maps.

Key Insights and Theoretical Breakthroughs

Unlike previous "path splines" (P-splines) which can result in stochastic, non-deterministic paths, transport splines ensure that every particle follows a single, smooth, deterministic trajectory. The authors prove that in the one-dimensional case, transport splines coincide with the theoretically ideal (but usually intractable) E-splines.

By reducing the problem to $N$ pairwise optimal transport computations and Euclidean splines, the method avoids the "curse of dimensionality" and the heavy optimization (like Semidefinite Programming) required by competing methods. Furthermore, this paper provides the first quantitative approximation guarantees in Wasserstein space, showing an $O(\delta^2)$ convergence rate in the Gaussian (Bures-Wasserstein) setting, mirroring classical results for Euclidean splines.

Experimental Results

Visual Fidelity and Smoothness

Qualitative results demonstrate that transport splines produce much more natural, "fluid-like" transitions between distributions compared to piecewise linear interpolation.

Comparison between linear and cubic spline interpolation on Wasserstein space.

N-Body Physical Systems

The method was tested on a simulation of N-body physical systems to show how it reconstructs particle trajectories in a physical context. The transport splines successfully recover the underlying dynamics from sparse temporal snapshots.

Reconstruction of N-body trajectories using natural cubic spline interpolation with 5 knots compared to true trajectories.

Performance and Scalability

For Gaussian measures, the method requires only one $d \times d$ matrix inversion and simple multiplications per sample point. In the general case, the complexity is dominated by $N$ pairwise optimal transport computations, which can be solved in near-linear time using modern algorithms like Sinkhorn iterations. This represents a significant speedup over prior state-of-the-art methods that required solving complex Semidefinite Programs (SDPs).

Conclusion and Future Work

Transport splines offer a computationally efficient and theoretically grounded method for smooth interpolation in Wasserstein space. While the current approximation guarantees are limited to the Gaussian setting, the algorithm itself is general. Future work includes developing "smoothing spline" versions to handle noisy data and exploring higher-order accuracy schemes through more accurate velocity field approximations.

Summary updated

Abstract

We propose a new method for smoothly interpolating probability measures using the geometry of optimal transport. To that end, we reduce this problem to the classical Euclidean setting, allowing us to directly leverage the extensive toolbox of spline interpolation. Unlike previous approaches to measure-valued splines, our interpolated curves (i) have a clear interpretation as governing particle flows, which is natural for applications, and (ii) come with the first approximation guarantees on Wasserstein space. Finally, we demonstrate the broad applicability of our interpolation methodology by fitting surfaces of measures using thin-plate splines.
BibTeX
@inproceedings{chewi2021fast,
  author = {Sinho Chewi and Julien Clancy and Thibaut Le Gouic and Philippe Rigollet and George Stepaniants and Austin Stromme},
  title = {{Fast and Smooth Interpolation on Wasserstein Space}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=6QYoszHQqxb},
}
Figure