Optimal transport group
PublicationsClicking on an image will provide a brief description of the corresponding paper (if available).
(SPOT) Sliced Optimal Partial Transport, to appear in CVPR 2023 (2023) [preprint] [details]
We give an adapted version of the Hungarian method to efficiently solve one-dimensional partial OT problems. This is then used for applying partial sliced OT to geometric problems such as noisy shape registration.
(LinOTMS) 3d virtual histology reveals pathological alterations of cerebellar granule cells in multiple sclerosis, (2022) [preprint] [details]
We apply the workflow of (PNAS21), involving linearized optimal transport, to the analysis of multiple sclerosis and its effects on cerebellar granule cells.
(EntropicTransfer) Entropic transfer operators, (2022) [preprint] [code] [details]
Entropic optimal transport is used to regularize a naive discretization of the transfer operator for dynamical systems. We proof that the regularization ensures convergence of the discretization in the limit, on length scales above the entropic blur. This allows for the numerical approximation of spectral analysis of dynamical systems on relatively primitive input data, such as observed discrete noisy trajectories.
(SemiDiscreteUnbalanced) Semi-discrete unbalanced optimal transport and quantization, (2018) [preprint] [details]
We combine the concepts of semi-discrete transport with unbalanced transport and generalize the `tessellation' formulations for semi-discrete classical optimal transport. The intrinsic length scale of unbalanced transport leads to interesting effects. Finally, we study the unbalanced quantization problem and its asymptotic behaviour in the limit of infinitely many points.
(HKDiracBarycenter) Hellinger-Kantorovich barycenter between Dirac measures, ESAIM: Control, Optimisation and Calculus of Variations 29, 19 (2023) [published version] [preprint] [details]
While the barycenter between a collection of Dirac measures is trivial for the Wasserstein-2 metric, it was observed in (HKBarycenter) that in the Hellinger--Kantorovich metric it exhibits a very complex behaviour. In this article we study this structure in more detail, in particular the dependency on the length scale, the relation between empirical and population barycenter, and duality.
(AsymptoticDomDec) Asymptotic analysis of domain decomposition for optimal transport, Numerische Mathematik (2023) [published version] [preprint] [code] [details]
The asymptotic behaviour of domain decomposition for optimal transport is studied in the limit of infinitely fine cells. Under suitable conditions this converges to a continuity equation for the coupling on the product space where the momentum field is purely `horizontal' and induced by a limit version of the domain decomposition algorithm. The result suggest that the number of iterations for domain decomposition scales linear with the problem resolution. In combination with coarse-to-fine schemes this could even be reduced to a logarithmic number of iterations and hence supports the numerical findings of (EntropicDomDec).
(BranchedTransportDual) Duality in branched transport and urban planning, Applied Mathematics & Optimization 86, 45 (2022) [published version] [preprint] [details]
This is a companion work to (BranchedTransportBilevel) in which related results are established via a different proof strategy based on a generalization of the Kantorovich--Rubinstein duality.
(BranchedTransportBilevel) Formulation of branched transport as geometry optimization, Journal de Mathématiques Pures et Appliquées 163, 739-779 (2022) [published version] [preprint] [details]
The formation of ramified transport networks has been modelled mathematically via the branched transport and urban planning formulation. For the original urban planning formulation an equivalent branched transport formulation has been shown. In this article we extend the equivalence to a more general set of costs on both sides. The proof strategy is based on explicit translation of minimizers between the two problems.
(GameLearning) Data-driven entropic spatially inhomogeneous evolutionary games, European Journal of Applied Mathematics (2022) [published version] [preprint] [details]
We propose a novel class of models for interacting particles based on spatially inhomogeneous evolutionary games with entropic regularization and then propose an inference functional to learn the agents' payoff function from observations of interactions.
(PNAS21) Three-dimensional virtual histology of the human hippocampus based on phase-contrast computed tomography, PNAS, 118 (48) e2113835118 (2021) [published version] [details]
Phase-contrast X-ray computed tomography is used to generate high-resolution large-volume 3d images of human brain tissue samples, including both Alzheimer’s-diseased patients and a control group. After automated segmentation and feature extraction of certain cell nuclei each sample can be represented as a point cloud on cell feature space. We use the framework of linearized optimal transport to study the population of samples and provide a preliminary identification of the main mode of variation between pathological and control group.
(UnbalancedLOT) The Linearized Hellinger-Kantorovich Distance, SIAM Journal on Imaging Sciences 15(1), 45-83 (2022) [published version] [preprint] [code] [details]
The Wasserstein-2 distance exhibits a weak Riemannian structure, including notions of tangent spaces, logarithmic and exponential maps. This structure has been leveraged successfully for a local linearization scheme which reduces the computational load and provides a linear embedding which is useful for subsequent data analysis tasks. In this article we generalize this approach to the unbalanced Hellinger-Kantorovich distance, which allows the approach to deal with local mass fluctuations in a more refined way.
(EntropicDomDec) Domain decomposition for entropy regularized optimal transport, Numerische Mathematik (2021) [published version] [preprint] [code] [details]
We study a domain decomposition algorithm for entropic optimal transport. Unlike the unregularized version it converges to the optimal solution under very mild assumptions. We bound the convergence rate and show that it can be very slow on malicous counter-examples. Conversely, on `nice' geometric problems we find empirically that it converges quickly. A computationally efficient implementation is discussed that compares favourably to a single Sinkhorn algorithm and which can be parallelized efficiently.
(HKBarycenter) Barycenters for the Hellinger-Kantorovich distance over Rd, SIAM Journal on Mathematical Analysis 53 (1), 62-110 (2021) [published version] [preprint] [details]
We study the barycenter of the HK metric. Analogously to the Wasserstein barycenter it can be formulated equivalently as a `coupled-two-marginal' formulation and as a multi-marginal formulation. The HK barycenter between Dirac measures is analyzed in detail. We find that it differs substantially from the Wasserstein barycenter by exhibiting a local `clustering' behaviour.
(DynamicPET-Numerics) Dynamic Cell Imaging in PET with Optimal Transport Regularization, IEEE Trans Med Imaging 39(5), 1626-1635 (2020) [published version] [preprint] [details]
We apply optimal transport as a temporal regularization for the reconstruction of particle trajectories from low intensity PET data. The regularization is in essence the "energy" of the trajectory in Wasserstein-2 space. This is a numerical proof-of-concept article. A more detailed mathematical analysis will follow.
(GraphTransport) Computation of Optimal Transport on Discrete Metric Measure Spaces, Numerische Mathematik 144, 157–200 (2020) [published version] [preprint] [details]
On a discrete metric space the Wasserstein-2 distance does not induce a geodesic space. This implies that there is no displacement interpolation and no notion of a gradient flow. Jan Maas proposed a modified distance by modifying the Benamou--Brenier formula for discrete spaces, based on a Markov kernel. In this article we propose a consistent time-discretization of the optimization problem and a corresponding optimization scheme based on proximal splitting. This allows, for instance, to numerically simulate the heat equation with respect to the Markov kernel as a gradient flow with respect to the new distance.
(SparseScaling) Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems, SIAM Journal on Scientific Computing (SISC) 41(3), A1443-A1481 (2019) [published version] [preprint] [code] [details]
This article builds on (UnbalancedScaling) and discusses some adaptions to the scaling algorithms for entropy regularized transport problems, for more robust and efficient numerical implementation. A log-domain stabilization and epsilon-scaling remedy diverging scaling factors and slow convergence as regularization approaches zero; adaptive truncation of the kernel and a coarse-to-fine scheme similar to (ShortCuts) reduce the requied memory. A new complexity analysis of the Sinkhorn algorithm, based on a comparison to the auction algorithm is developed. Numerical examples demonstrate that the modified algorithm can solve a variety of large transport-type problems with small regularization.
(UnbalancedW1-Dynamic) Dynamic Models of Wasserstein-1-Type Unbalanced Transport, ESAIM: Control, Optimisation and Calculus of Variations 25, 23 (2019) [published version] [preprint] [details]
This article relates (StaticWFR) with (UnbalancedW1): static and dynamic formulations for unbalanced Wasserstein-1-type transport models are given. In particular it is shown that under suitable assumptions every dynamic model can be rewritten as a (computationally more attractive) static model. Conversely, we study which static models have a dynamic interpretation.
(UnbalancedW1) A Framework for Wasserstein-1-Type Metrics, Journal of Convex Analysis 26 (2), 353-396 (2019) [published version] [preprint] [details]
In (WFR), (StaticWFR) and (UnbalancedScaling) models for unbalanced transport were studied, where mass can be created or annihilated, with a focus on Wasserstein-2-type transport models. In this article we develop an analogous framework for the Wasserstein-1 metric. The extended models allow to combine the W-1 distance with other local similarity measures. In particular the reformulation as a min-cost flow problem is preserved, which can be solved efficiently. Numerical examples illustrate the robustness of the resulting unbalanced discrepancy measures on noisy data.
(StaticWFR) Unbalanced Optimal Transport: Dynamic and Kantorovich Formulations, Journal of Functional Analysis 274 (11), 3090-3123 (2018) [published version] [preprint] [details]
This article is a direct continuation of the work in (WFR). We study the geometry of the Wasserstein-Fisher-Rao interpolation and in particular provide a Kantorovich-like static reformulation of the dynamic problem. Since the proof of equivalence between the two formulations hinges only on rather general properties of the functional, we generalize the results to cover a large class of dynamic extensions of optimal transport. This may be an important step in finding efficient numerical solvers to generalizations of dynamic optimal transport.
(UnbalancedScaling) Scaling Algorithms for Unbalanced Transport Problems, Mathematics of Computation 87, 2563-2609 (2018) [published version] [preprint] [details]
A family of scaling algorithms for entropy regularized transport-type problems is introduced, that generalize the well-known Sinkhorn algorithm for standard optimal transport. Applications involve unbalanced transport problems (in a formulation given by [Liero, Mielke, Savaré], related to the formulation given in (StaticWFR)), JKO-type gradient flow schemes and (unbalanced) barycenters. The article provides an analysis of the algorithms in a continuous setting, comments on practical implementation for discretized problems and several numerical examples.
(WFR) An Interpolating Distance between Optimal Transport and Fisher-Rao Metrics, Foundations of Computational Mathematics 18: 1-44 (2018) [published version] [preprint] [details]
Based on the dynamic formulation of optimal transport due to Benamou and Brenier, this paper introduces an interpolation between the classical L2 optrimal transport distance and the Fisher-Rao metric. For this a source term is added to the continuity equation which allows for generation and removal of mass. We analyze the corresponding optimization problem in the context of convex optimization and study in particular geodesics between Dirac measures. Finally, a numerical scheme is presented and some examples illustrate the usefulness of this particular growth term for image interpolation.
(EntropicOT) Convergence of Entropic Schemes for Optimal Transport and Gradient Flows, SIAM Journal on Mathematical Analysis 49 (2), 1385-1418 (2017) [published version] [preprint] [details]
Entropy regularization has recently been re-introduced as an efficient numerical method for approximately solving problems involving optimal transport. In this article we investigate the convergence to the unregularized problem. We show that the regularized transport functional Gamma-converges to the standard functional in the limit of vanishing regularization. Analogously, we show that the implicit time-discrete Wasserstein gradient flow scheme for non-linear diffusion, with a regularized transport functional, converges to the same PDE-limit as the unregularized scheme, if regularization decreases sufficiently fast with decreasing time-step size.
(ImageAssignment) Image Labeling by Assignment, Journal of Mathematical Imaging and Vision 58(2), 211-238 (2017) [published version] [preprint] [details]
This article introduces a non-convex framework for the image labelling problem. A (fuzzy) labelling of an image pixel is represented by a discrete probability distribution. Starting from the completely undecided fuzzy labelling, the final image labelling is obtained by following a Fisher-Rao gradient flow, where the energy is determined by the discrepancy of a pixel labelling from its local expectation (determined by the observed data) and the labels of the neighbouring pixels. The flexible mathematical formulation allows for application to rather different problems.
(ShortCuts) A Sparse Multi-Scale Algorithm for Dense Optimal Transport, Journal of Mathematical Imaging and Vision 56 (2): 238-259 (2016) [published version] [preprint] [code] [details]
This is an extension of (SSVM'15). Analogous to continuous optimal transport, a framework for locally verifying global optimality of a given coupling is developed, leveraging the geometric structure of the underlying cost function. This leads to a sparse multi-scale algorithm for large dense problems. Various cost functions (including the squared Euclidean distance and the squared geodesic distance on the sphere) and noisy variants thereof are detailed explicitly. Numerical experiments demonstrate a substantial decrease in memory requirements and a speed-up of around two orders of magnitude compared to the naive dense approach.
(WassersteinModes) Globally Optimal Joint Image Segmentation and Shape Matching based on Wasserstein Modes, Journal of Mathematical Imaging and Vision 52 (3): 436-458 (2015) [published version] [preprint] [details]
This is a more detailed analysis of the ideas developed in (EMMCVPR'13) for object segmentation and matching with a prototype template. Based on the relation developed in (ShapeMeasures) we use contour-based statistical learning methods to obtain a set of non-isometric Wasserstein modes to describe typical deformations of the template. Locally adaptive appearance models are studied and different optimization schemes are discussed in detail.
(ShapePriorGW) Modelling convex shape priors and matching based on the Gromov-Wasserstein distance, Journal of Mathematical Imaging and Vision 46 (1): 143-159 (2012) [pdf] [published version] [details]
Representing shapes by so called metric measure-spaces (mm-spaces) and comparing them by the Gromov-Wasserstein distance has proven to be an elegant way to overcome issues like reparametrization ambiguity and to abstract from transformations that a shape can undergo while still remaining basically the same shape. However the involved optimization problems are highly non-convex. In this paper we present a series of suitable approximations to the Gromov-Wasserstein functional and arrive at a modified linear optimal transport problem for finding a registration between a given shape template and its most probable instance within the query image. To our knowledge this is the first time that a shape prior functional is presented, that is both convex and invariant under various geometric transformations.
Conference Articles (Peer Reviewed)
(SSVM'17) Optimal Transport for Manifold-Valued Images, Proceedings of the 6th International Conference on Scale Space and Variational Methods in Computer Vision (2017) [pdf] [published version] [details]
An extension of optimal transport to non-scalar signals such as color images is constructed by lifting the original signals to non-negative measures on a higher dimensional space. It is natural to use unbalanced transport in this setting. Numerical optimization is handled with the algorithms developed in (UnbalancedScaling) and (SparseScaling). We give examples for interpolation between color images in different color spaces as well as a simple classification example on the MNIST dataset.
(SSVM'15) A sparse algorithm for dense optimal transport, Proceedings of the 5th International Conference on Scale Space and Variational Methods in Computer Vision (2015) [pdf] [published version] [details]
This is a continuation of the work started in (SSVM'13) to develop sparse algorithms for solving dense discrete optimal transport problems. In (SSVM'13) the structure of the cost function is only exploited implicitly, hoping that only few hierarchical consistency checks are necessary. Here on the other hand, the structure is explicitly used, resulting in `truely' sparse algorithms. Compared to (SSVM'13) this approach is less flexible in terms of cost functions, but more flexible in terms of which algorithms one can accelerate, resulting in lower running-times.
(EMMCVPR'13) Object Segmentation by Shape Matching with Wasserstein Modes, Proceedings of the 9th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (2013) [pdf] [published version] [details]
In (ShapePriorGW) we used optimal transport to compute an assignment between a reference template and its most likely counterpart in a query image. Geometric invariance was obtained by a particular cost function, computed in a pre-processing step, based on an approximation to the Gromov-Wasserstein distance. In this paper we explicitly optimize over the embeddings of the reference template into the image domain. Standard squared Euclidean distance is used as cost function, making the rich Monge theory of optimal transport applicable. Using the manifold structure of measures, equipped with optimal transport, we can describe isometries and non-isometric deformations in a unified way. Global optimality of the non-convex model is obtained via a branch and bound scheme, based on locally adaptive convex relaxations.
(SSVM'13) A Hierarchical Approach to Optimal Transport, Proceedings of the 4th International Conference on Scale Space and Variational Methods in Computer Vision (2013) [pdf] [published version] [details]
The linear assignment and optimal transport problem are not only important tools in our own line of research but pervade models in computer vision and machine learning. Practical problems often come with a cost function which is far from arbitrary, but in fact rather regular. Unfortunately efficient solvers that exploit the structure of cost functions are rare (except for the squared Euclidean distance, of course). In this paper we discuss an extension of the famous auction algorithm, to turn large, dense optimal transport problems into sparse subproblems, guaranteeing global optimality by a hierarchical consistency check. We observe a significant gain in performance on a wide range of test problems (in particular beyond squared Euclidean distance in real vector spaces).
(SSVM'11) Weakly Convex Coupling Continuous Cuts and Shape Priors, Proceedings of the 3rd International Conference on Scale Space and Variational Methods in Computer Vision (2011) [pdf] [published version] [details]
In this paper we demonstrate that enhancing binary foreground/background segmentation by the aid of a shape prior is in principle possible in a convex variational framework. Two simple shape models, both represented by Markov random fields (MRF), are considered. The segmentation problem is formulated in a convex variational way via the famous continuous cuts functional. A convex shape prior functional is obtained from the shape model through the local polytope relaxation of the underlying MRFs. The two components are coupled by a quadratic term yielding a convex overall functional which we optimize globally with a recent algorithm from convex optimization.
(ShapeMeasures) Contour Manifolds and Optimal Transport, (2013) [preprint] [details]
In (EMMCVPR'13) we represented shapes by measures with indicator functions as densities, using the pseudo-Riemannian structure of the Wasserstein space of measures for modelling isometries and statistical variations. In this paper we provide a mathematical study of the shape measure representation and its relation to the contour description. It turns out that both representations are equivalent in the sense that the two corresponding manifolds are diffeomorphic. We claim that this can be used to combine the usefulness of the natural linear structures on indicator functions as well as on tangent-space approximations to contour manifolds for image processing tasks.
Isometry Invariant Shape Priors for Variational Image Segmentation, Universität Heidelberg (2014) [published version]
The Random Discrete Action for 2-Dimensional Spacetime, Class. Quantum Grav. 28 105018 (2011) [published version] [preprint]
Pulses of chaos synchronization in coupled map chains with delayed transmission, Phys. Rev. E 80, 047203 (2009) [published version]