JLJohannes von Lindheim

Johannes von Lindheim

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Johannes von Lindheim has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Generalized Iterative Scaling for Regularized Optimal Transport with Affine Constraints: Application Examples

    by Johannes von Lindheim, Gabriele Steidl

    We demonstrate the relevance of an algorithm called generalized iterative scaling (GIS) or simultaneous multiplicative algebraic reconstruction technique (SMART) and its rescaled block-iterative version (RBI-SMART) in the field of optimal transport (OT). Many OT problems can be tackled through the use of entropic regularization by solving the Schrödinger problem, which is an information projection problem, that is, with respect to the Kullback--Leibler divergence. Here we consider problems that have several affine constraints. It is well-known that cyclic information projections onto the individual affine sets converge to the solution. In practice, however, even these individual projections are not explicitly available in general. In this paper, we exchange them for one GIS iteration. If this is done for every affine set, we obtain RBI-SMART. We provide a convergence proof using an interpretation of these iterations as two-step affine projections in an equivalent problem. This is done in a slightly more general setting than RBI-SMART, since we use a mix of explicitly known information projections and GIS iterations. We proceed to specialize this algorithm to several OT applications. First, we find the measure that minimizes the regularized OT divergence to a given measure under moment constraints. Second and third, the proposed framework yields an algorithm for solving a regularized martingale OT problem, as well as a relaxed version of the barycentric weak OT problem. Finally, we show an approach from the literature for unbalanced OT problems.


  • Open Access

    Simple approximative algorithms for free-support Wasserstein barycenters

    by Johannes von Lindheim

    Computing Wasserstein barycenters of discrete measures has recently attracted considerable attention due to its wide variety of applications in data science. In general, this problem is NP-hard, calling for practical approximative algorithms. In this paper, we analyze a well-known simple framework for approximating Wasserstein- $${\varvec{p}}$$p barycenters, where we mainly consider the most common case $${\varvec{p}}={\varvec{2}}$$p=2 and $${\varvec{p}}={\varvec{1}}$$p=1 , which is not as well discussed. The framework produces sparse support solutions and shows good numerical results in the free-support setting. Depending on the desired level of accuracy, this requires only $${\varvec{N}}-{\varvec{1}}$$N-1 or $${\varvec{N(N}}-{\varvec{1)/2 }}$$N(N-1)/2 standard two-marginal optimal transport (OT) computations between the $${\varvec{N}}$$N input measures, respectively, which is fast, memory-efficient and easy to implement using any OT solver as a black box. What is more, these methods yield a relative error of at most $${\varvec{N}}$$N and $${\varvec{2}}$$2 , respectively, for both $${\varvec{p}}={\varvec{ 1, 2}}$$p=1,2 . We show that these bounds are practically sharp. In light of the hardness of the problem, it is not surprising that such guarantees cannot be close to optimality in general. Nevertheless, these error bounds usually turn out to be drastically lower for a given particular problem in practice and can be evaluated with almost no computational overhead, in particular without knowledge of the optimal solution. In our numerical experiments, this guaranteed errors of at most a few percent.


  • Open Access

    Simple Approximative Algorithms for Free-Support Wasserstein Barycenters

    by Johannes von Lindheim

    Computing Wasserstein barycenters of discrete measures has recently attracted considerable attention due to its wide variety of applications in data science. In general, this problem is NP-hard, calling for practical approximative algorithms. In this paper, we analyze a well-known simple framework for approximating Wasserstein-$p$ barycenters, where we mainly consider the most common case $p=2$ and $p=1$, which is not as well discussed. The framework produces sparse support solutions and shows good numerical results in the free-support setting. Depending on the desired level of accuracy, this requires only $N-1$ or $N(N-1)/2$ standard two-marginal optimal transport (OT) computations between the $N$ input measures, respectively, which is fast, memory-efficient and easy to implement using any OT solver as a black box. What is more, these methods yield a relative error of at most $N$ and $2$, respectively, for both $p=1, 2$. We show that these bounds are practically sharp. In light of the hardness of the problem, it is not surprising that such guarantees cannot be close to optimality in general. Nevertheless, these error bounds usually turn out to be drastically lower for a given particular problem in practice and can be evaluated with almost no computational overhead, in particular without knowledge of the optimal solution. In our numerical experiments, this guaranteed errors of at most a few percent.

  • Open Access

    Unbalanced Multi-marginal Optimal Transport

    by Florian Beier, Johannes von Lindheim, Sebastian Neumayer, Gabriele Steidl

    Entropy-regularized optimal transport and its multi-marginal generalization have attracted increasing attention in various applications, in particular due to efficient Sinkhorn-like algorithms for computing optimal transport plans. However, it is often desirable that the marginals of the optimal transport plan do not match the given measures exactly, which led to the introduction of the so-called unbalanced optimal transport. Since unbalanced methods were not examined for the multi-marginal setting so far, we address this topic in the present paper. More precisely, we introduce the unbalanced multi-marginal optimal transport problem and its dual and show that a unique optimal transport plan exists under mild assumptions. Furthermore, we generalize the Sinkhorn algorithm for regularized unbalanced optimal transport to the multi-marginal setting and prove its convergence. For cost functions decoupling according to a tree, the iterates can be computed efficiently. At the end, we discuss three applications of our framework, namely two barycenter problems and a transfer operator approach, where we establish a relation between the barycenter problem and the multi-marginal optimal transport with an appropriate tree-structured cost function.


  • Open Access

    Unbalanced Multi-Marginal Optimal Transport

    by Florian Beier, Johannes von Lindheim, Sebastian Neumayer, Gabriele Steidl

    Entropy regularized optimal transport and its multi-marginal generalization have attracted increasing attention in various applications, in particular due to efficient Sinkhorn-like algorithms for computing optimal transport plans. However, it is often desirable that the marginals of the optimal transport plan do not match the given measures exactly, which led to the introduction of the so-called unbalanced optimal transport. Since unbalanced methods were not examined for the multi-marginal setting so far, we address this topic in the present paper. More precisely, we introduce the unbalanced multi-marginal optimal transport problem and its dual, and show that a unique optimal transport plan exists under mild assumptions. Further, we generalize the Sinkhorn algorithm for regularized unbalanced optimal transport to the multi-marginal setting and prove its convergence. If the cost function decouples according to a tree, the iterates can be computed efficiently. At the end, we discuss three applications of our framework, namely two barycenter problems and a transfer operator approach, where we establish a relation between the barycenter problem and the multi-marginal optimal transport with an appropriate tree-structured cost function.

  • Transfer operators from optimal transport plans for coherent set detection

    by Péter Koltai, Johannes von Lindheim, Sebastian Neumayer, Gabriele Steidl


  • Open Access

    Transfer Operators from Optimal Transport Plans for Coherent Set Detection

    by Péter Koltai, Johannes von Lindheim, Sebastian Neumayer, Gabriele Steidl

    The topic of this study lies in the intersection of two fields. One is related with analyzing transport phenomena in complicated flows.For this purpose, we use so-called coherent sets: non-dispersing, possibly moving regions in the flow's domain. The other is concerned with reconstructing a flow field from observing its action on a measure, which we address by optimal transport. We show that the framework of optimal transport is well suited for delivering the formal requirements on which a coherent-set analysis can be based on. The necessary noise-robustness requirement of coherence can be matched by the computationally efficient concept of unbalanced regularized optimal transport. Moreover, the applied regularization can be interpreted as an optimal way of retrieving the full dynamics given the extremely restricted information of an initial and a final distribution of particles moving according to Brownian motion.