This paper details a general numerical framework to approximate solutions to linear programs related to optimal transport. The general idea is to introduce an entropic regularization of the initial linear program. This regularized problem corresponds to a Kullback--Leibler Bregman divergence projection of a vector (representing some initial joint distribution) on the polytope of constraints. We show that for many problems related to optimal transport, the set of linear constraints can be split in an intersection of a few simple constraints, for which the projections can be computed in closed form. This allows us to make use of iterative Bregman projections (when there are only equality constraints) or, more generally, Bregman--Dykstra iterations (when inequality constraints are involved). We illustrate the usefulness of this approach for several variational problems related to optimal transport: barycenters for the optimal transport metric, tomographic reconstruction, multimarginal optimal transport, and in particular its application to Brenier's relaxed solutions of incompressible Euler equations, partial unbalanced optimal transport, and optimal transport with capacity constraints.

We present a novel geometric approach for solving the stereo problem for an arbitrary number of images (= or >2). It is based upon the definition of a variational principle that must be satisfied by the surfaces of the objects in the scene and their images. The Euler-Lagrange equations that are deduced from the variational principle provide a set of partial differential equations (PDE's) that are used to deform an initial set of surfaces which then move toward the objects to be detected. The level set implementation of these PDE's potentially provides an efficient and robust way of achieving the surface evolution and to deal automatically with changes in the surface topology during the deformations, i.e., to deal with multiple objects. Results of an implementation of our theory also dealing with occlusion and visibility are presented on synthetic and real images.

This paper introduces a new class of algorithms for optimization problems involving optimal transportation over geometric domains. Our main contribution is to show that optimal transportation can be made tractable over large domains used in graphics, such as images and triangle meshes, improving performance by orders of magnitude compared to previous work. To this end, we approximate optimal transportation distances using entropic regularization. The resulting objective contains a geodesic distance-based kernel that can be approximated with the heat kernel. This approach leads to simple iterative numerical schemes with linear convergence, in which each iteration only requires Gaussian convolution or the solution of a sparse, pre-factored linear system. We demonstrate the versatility and efficiency of our method on tasks including reflectance interpolation, color transfer, and geometry processing.

The forward electroencephalography (EEG) problem involves finding a potential V from the Poisson equation /spl nabla//spl middot/(/spl sigma//spl nabla/V)=f, in which f represents electrical sources in the brain, and /spl sigma/ the conductivity of the head tissues. In the piecewise constant conductivity head model, this can be accomplished by the boundary element method (BEM) using a suitable integral formulation. Most previous work uses the same integral formulation, corresponding to a double-layer potential. We present a conceptual framework based on a well-known theorem (Theorem 1) that characterizes harmonic functions defined on the complement of a bounded smooth surface. This theorem says that such harmonic functions are completely defined by their values and those of their normal derivatives on this surface. It allows us to cast the previous BEM approaches in a unified setting and to develop two new approaches corresponding to different ways of exploiting the same theorem. Specifically, we first present a dual approach which involves a single-layer potential. Then, we propose a symmetric formulation, which combines single- and double-layer potentials, and which is new to the field of EEG, although it has been applied to other problems in electromagnetism. The three methods have been evaluated numerically using a spherical geometry with known analytical solution, and the symmetric formulation achieves a significantly higher accuracy than the alternative methods. Additionally, we present results with realistically shaped meshes. Beside providing a better understanding of the foundations of BEM methods, our approach appears to lead also to more efficient algorithms.

This article details two approaches to compute barycenters of measures using 1-D Wasserstein distances along radial projections of the input measures. The first method makes use of the Radon transform of the measures, and the second is the solution of a convex optimization problem over the space of measures. We show several properties of these barycenters and explain their relationship. We show numerical approximation schemes based on a discrete Radon transform and on the resolution of a non-convex optimization problem. We explore the respective merits and drawbacks of each approach on applications to two image processing problems: color transfer and texture mixing.

This paper introduces the generalized forward-backward splitting algorithm for minimizing convex functions of the form $F + \sum_{i=1}^n G_i$, where $F$ has a Lipschitz-continuous gradient and the $G_i$'s are simple in the sense that their Moreau proximity operators are easy to compute. While the forward-backward algorithm cannot deal with more than $n = 1$ non-smooth function, our method generalizes it to the case of arbitrary $n$. Our method makes an explicit use of the regularity of $F$ in the forward step, and the proximity operators of the $G_i$'s are applied in parallel in the backward step. This allows the generalized forward backward to efficiently address an important class of convex problems. We prove its convergence in infinite dimension, and its robustness to errors on the computation of the proximity operators and of the gradient of $F$. Examples on inverse problems in imaging demonstrate the advantage of the proposed methods in comparison to other splitting algorithms.

This paper studies sparse spikes deconvolution over the space of measures. We focus on the recovery properties of the support of the measure (i.e., the location of the Dirac masses) using total variation of measures (TV) regularization. This regularization is the natural extension of the $$\ell ^1$$ norm of vectors to the setting of measures. We show that support identification is governed by a specific solution of the dual problem (a so-called dual certificate) having minimum $$L^2$$ norm. Our main result shows that if this certificate is non-degenerate (see the definition below), when the signal-to-noise ratio is large enough TV regularization recovers the exact same number of Diracs. We show that both the locations and the amplitudes of these Diracs converge toward those of the input measure when the noise drops to zero. Moreover, the non-degeneracy of this certificate can be checked by computing a so-called vanishing derivative pre-certificate. This proxy can be computed in closed form by solving a linear system. Lastly, we draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, and provided the aforementioned dual certificate is non-degenerate, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero.

Abstract The recent advent of high-throughput single-cell molecular profiling is revolutionizing biology and medicine by unveiling the diversity of cell types and states contributing to development and disease. The identification and characterization of cellular heterogeneity is typically achieved through unsupervised clustering, which crucially relies on a similarity metric. We here propose the use of Optimal Transport (OT) as a cell-cell similarity metric for single-cell omics data. OT defines distances to compare, in a geometrically faithful way, high-dimensional data represented as probability distributions. It is thus expected to better capture complex relationships between features and produce a performance improvement over state-of-the-art metrics. To speed up computations and cope with the high-dimensionality of single-cell data, we consider the entropic regularization of the classical OT distance. We then extensively benchmark OT against state-of-the-art metrics over thirteen independent datasets, including simulated, scRNA-seq, scATAC-seq and single-cell DNA methylation data. First, we test the ability of the metrics to detect the similarity between cells belonging to the same groups (e.g. cell types, cell lines of origin). Then, we apply unsupervised clustering and test the quality of the resulting clusters. In our in-depth evaluation, OT is found to improve cell-cell similarity inference and cell clustering in all simulated and real scRNA-seq data, while its performances are comparable with Pearson correlation in scATAC-seq and single-cell DNA methylation data. All our analyses are reproducible through the OT-scOmics Jupyter notebook available at https://github.com/ComputationalSystemsBiology/OT-scOmics .

The abundance of unpaired multimodal single-cell data has motivated a growing body of research into the development of diagonal integration methods. However, the state-of-the-art suffers from the loss of biological information due to feature conversion and struggles with modality-specific populations. To overcome these crucial limitations, we here introduce scConfluence, a method for single-cell diagonal integration. scConfluence combines uncoupled autoencoders on the complete set of features with regularized Inverse Optimal Transport on weakly connected features. We extensively benchmark scConfluence in several single-cell integration scenarios proving that it outperforms the state-of-the-art. We then demonstrate the biological relevance of scConfluence in three applications. We predict spatial patterns for Scgn, Synpr and Olah in scRNA-smFISH integration. We improve the classification of B cells and Monocytes in highly heterogeneous scRNA-scATAC-CyTOF integration. Finally, we reveal the joint contribution of Fezf2 and apical dendrite morphology in Intra Telencephalic neurons, based on morphological images and scRNA.