Bernhard Schmitzer

Guillaume Carlier, Vincent Duval, Gabriel Peyré et al.

Replacing positivity constraints by an entropy barrier is popular to approximate solutions of linear programs. In the special case of the optimal transport problem, this technique dates back to the early work of Schrödinger. This approach has recently been used successfully to solve optimal transport related problems in several applied fields such as imaging sciences, machine learning and social sciences. The main reason for this success is that, in contrast to linear programming solvers, the resulting algorithms are highly parallelizable and take advantage of the geometry of the computational grid (e.g. an image or a triangulated mesh). The first contribution of this article is the proof of the $Γ$-convergence of the entropic regularized optimal transport problem towards the Monge-Kantorovich problem for the squared Euclidean norm cost function. This implies in particular the convergence of the optimal entropic regularized transport plan towards an optimal transport plan as the entropy vanishes. Optimal transport distances are also useful to define gradient flows as a limit of implicit Euler steps according to the transportation distance. Our second contribution is a proof that implicit steps according to the entropic regularized distance converge towards the original gradient flow when both the step size and the entropic penalty vanish (in some controlled way).

Bernhard Schmitzer

Scaling algorithms for entropic transport-type problems have become a very popular numerical method, encompassing Wasserstein barycenters, multi-marginal problems, gradient flows and unbalanced transport. However, a standard implementation of the scaling algorithm has several numerical limitations: the scaling factors diverge and convergence becomes impractically slow as the entropy regularization approaches zero. Moreover, handling the dense kernel matrix becomes unfeasible for large problems. To address this, we combine several modifications: A log-domain stabilized formulation, the well-known epsilon-scaling heuristic, an adaptive truncation of the kernel and a coarse-to-fine scheme. This permits the solution of larger problems with smaller regularization and negligible truncation error. A new convergence analysis of the Sinkhorn algorithm is developed, working towards a better understanding of epsilon-scaling. Numerical examples illustrate efficiency and versatility of the modified algorithm.

Bernhard Schmitzer, Benedikt Wirth

We consider a class of convex optimization problems modelling temporal mass transport and mass change between two given mass distributions (the so-called dynamic formulation of unbalanced transport), where we focus on those models for which transport costs are proportional to transport distance. For those models we derive an equivalent, computationally more efficient static formulation, we perform a detailed analysis of the model optimizers and the associated optimal mass change and transport, and we examine which static models are generated by a corresponding equivalent dynamic one. Alongside we discuss thoroughly how the employed model formulations relate to other formulations found in the literature.

Keaton Hamm, Caroline Moosmüller, Bernhard Schmitzer et al.

This paper aims at building the theoretical foundations for manifold learning algorithms in the space of absolutely continuous probability measures $\mathcal{P}_{\mathrm{a.c.}}(Ω)$ with $Ω$ a compact and convex subset of $\mathbb{R}^d$, metrized with the Wasserstein-2 distance $\mathbb{W}$. We begin by introducing a construction of submanifolds $Λ$ in $\mathcal{P}_{\mathrm{a.c.}}(Ω)$ equipped with metric $\mathbb{W}_Λ$, the geodesic restriction of $\mathbb{W}$ to $Λ$. In contrast to other constructions, these submanifolds are not necessarily flat, but still allow for local linearizations in a similar fashion to Riemannian submanifolds of $\mathbb{R}^d$. We then show how the latent manifold structure of $(Λ,\mathbb{W}_Λ)$ can be learned from samples $\{λ_i\}_{i=1}^N$ of $Λ$ and pairwise extrinsic Wasserstein distances $\mathbb{W}$ on $\mathcal{P}_{\mathrm{a.c.}}(Ω)$ only. In particular, we show that the metric space $(Λ,\mathbb{W}_Λ)$ can be asymptotically recovered in the sense of Gromov--Wasserstein from a graph with nodes $\{λ_i\}_{i=1}^N$ and edge weights $W(λ_i,λ_j)$. In addition, we demonstrate how the tangent space at a sample $λ$ can be asymptotically recovered via spectral analysis of a suitable ``covariance operator'' using optimal transport maps from $λ$ to sufficiently close and diverse samples $\{λ_i\}_{i=1}^N$. The paper closes with some explicit constructions of submanifolds $Λ$ and numerical examples on the recovery of tangent spaces through spectral analysis.

Florian Beier, Hancheng Bi, Clément Sarrazin et al.

In this paper, we are concerned with estimating the joint probability of random variables $X$ and $Y$, given $N$ independent observation blocks $(\boldsymbol{x}^i,\boldsymbol{y}^i)$, $i=1,\ldots,N$, each of $M$ samples $(\boldsymbol{x}^i,\boldsymbol{y}^i) = \bigl((x^i_j, y^i_{σ^i(j)}) \bigr)_{j=1}^M$, where $σ^i$ denotes an unknown permutation of i.i.d. sampled pairs $(x^i_j,y_j^i)$, $j=1,\ldots,M$. This means that the internal ordering of the $M$ samples within an observation block is not known. We derive a maximum-likelihood inference functional, propose a computationally tractable approximation and analyze their properties. In particular, we prove a $Γ$-convergence result showing that we can recover the true density from empirical approximations as the number $N$ of blocks goes to infinity. Using entropic optimal transport kernels, we model a class of hypothesis spaces of density functions over which the inference functional can be minimized. This hypothesis class is particularly suited for approximate inference of transfer operators from data. We solve the resulting discrete minimization problem by a modification of the EMML algorithm to take addional transition probability constraints into account and prove the convergence of this algorithm. Proof-of-concept examples demonstrate the potential of our method.

Bernhard Schmitzer, Klaus P. Schäfers, Benedikt Wirth

We propose a novel dynamic image reconstruction method from PET listmode data that could be particularly suited to tracking single or small numbers of cells. In contrast to conventional PET reconstruction our method combines the information from all detected events not only to reconstruct the dynamic evolution of the radionuclide distribution, but also to improve the reconstruction at each single time point by enforcing temporal consistency. This is achieved via optimal transport regularization where in principle, among all possible temporally evolving radionuclide distributions consistent with the PET measurement, the one is chosen with least kinetic motion energy. The reconstruction is found by convex optimization so that there is no dependence on the initialization of the method. We study its behaviour on simulated data of a human PET system and demonstrate its robustness even in settings with very low radioactivity. In contrast to previously reported cell tracking algorithms, our technique is oblivious to the number of tracked cells. Without any additional complexity one or multiple cells can be reconstructed, and the model automatically determines the number of particles. For instance, four radiolabelled cells moving at a velocity of 3.1 mm/s and a PET recorded count rate of 1.1 cps (for each cell) could be simultaneously tracked with a tracking accuracy of 5.3 mm inside a simulated human body.

Matthias Erbar, Martin Rumpf, Bernhard Schmitzer et al.

In this paper we investigate the numerical approximation of an analogue of the Wasserstein distance for optimal transport on graphs that is defined via a discrete modification of the Benamou--Brenier formula. This approach involves the logarithmic mean of measure densities on adjacent nodes of the graph. For this model a variational time discretization of the probability densities on graph nodes and the momenta on graph edges is proposed. A robust descent algorithm for the action functional is derived, which in particular uses a proximal splitting with an edgewise nonlinear projection on the convex subgraph of the logarithmic mean. Thereby, suitable chosen slack variables avoid a global coupling of probability densities on all graph nodes in the projection step. For the time discrete action functional $Γ$--convergence to the time continuous action is established. Numerical results for a selection of test cases show qualitative and quantitative properties of the optimal transport on graphs. Finally, we use our algorithm to implement a JKO scheme for the gradient flow of the entropy in the discrete transportation distance, which is known to coincide with the underlying Markov semigroup, and test our results against a classical backward Euler discretization of this discrete heat flow.

Bernhard Schmitzer, Benedikt Wirth

We propose a unifying framework for generalising the Wasserstein-1 metric to a discrepancy measure between nonnegative measures of different mass. This generalization inherits the convexity and computational efficiency from the Wasserstein-1 metric, and it includes several previous approaches from the literature as special cases. For various specific instances of the generalized Wasserstein-1 metric we furthermore demonstrate their usefulness in applications by numerical experiments.

Freddie Åström, Stefania Petra, Bernhard Schmitzer et al.

We introduce a novel geometric approach to the image labeling problem. Abstracting from specific labeling applications, a general objective function is defined on a manifold of stochastic matrices, whose elements assign prior data that are given in any metric space, to observed image measurements. The corresponding Riemannian gradient flow entails a set of replicator equations, one for each data point, that are spatially coupled by geometric averaging on the manifold. Starting from uniform assignments at the barycenter as natural initialization, the flow terminates at some global maximum, each of which corresponds to an image labeling that uniquely assigns the prior data. Our geometric variational approach constitutes a smooth non-convex inner approximation of the general image labeling problem, implemented with sparse interior-point numerics in terms of parallel multiplicative updates that converge efficiently.

Bernhard Schmitzer, Christoph Schnörr

A functional for joint variational object segmentation and shape matching is developed. The formulation is based on optimal transport w.r.t. geometric distance and local feature similarity. Geometric invariance and modelling of object-typical statistical variations is achieved by introducing degrees of freedom that describe transformations and deformations of the shape template. The shape model is mathematically equivalent to contour-based approaches but inference can be performed without conversion between the contour and region representations, allowing combination with other convex segmentation approaches and simplifying optimization. While the overall functional is non-convex, non-convexity is confined to a low-dimensional variable. We propose a locally optimal alternating optimization scheme and a globally optimal branch and bound scheme, based on adaptive convex relaxation. Combining both methods allows to eliminate the delicate initialization problem inherent to many contour based approaches while remaining computationally practical. The properties of the functional, its ability to adapt to a wide range of input data structures and the different optimization schemes are illustrated and compared by numerical experiments.

Bernhard Schmitzer, Christoph Schnörr

Describing shapes by suitable measures in object segmentation, as proposed in [24], allows to combine the advantages of the representations as parametrized contours and indicator functions. The pseudo-Riemannian structure of optimal transport can be used to model shapes in ways similar as with contours, while the Kantorovich functional enables the application of convex optimization methods for global optimality of the segmentation functional. In this paper we provide a mathematical study of the shape measure representation and its relation to the contour description. In particular we show that the pseudo-Riemannian structure of optimal transport, when restricted to the set of shape measures, yields a manifold which is diffeomorphic to the manifold of closed contours. A discussion of the metric induced by optimal transport and the corresponding geodesic equation is given.