VIALARD Francois Xavier

In recent years, optimal transport has gained popularity in machine learning as a way to compare probability measures. Unlike more traditional dissimilarities for probability distributions, such as Kullback-Leibler divergence, optimal transport distances (or Wasserstein distances) allow for the comparison of distributions with disjoint supports by taking into account the geometry of the underlying space. This advantage is however hampered by the fact that these distances are usually computed by solving a linear program, which poses, when the underlying space is high dimensional, well documented statistical challenges commonly referred to as the ``dimensional curse''. Beyond this purely metric aspect, another interest of optimal transport theory is that it provides mathematical tools to study maps that can transform, or transport, one measure into another. Such maps play an increasingly important role in various fields of science (biology, brain imaging) or subfields of machine learning (generative models, domain adaptation), among others. In this thesis, we propose a new estimation framework for computing variants of Wasserstein distances. The goal is to reduce the effects of high dimensionality by taking advantage of the low dimensional structures hidden in the distributions. This can be done by projecting the measures onto a subspace chosen to maximize the Wasserstein distance between their projections. In addition to this new methodology, we show that this framework is more broadly consistent with a link between regularization of Wasserstein distances and robustness.In the following contribution, we start from the same problem of estimating the optimal transport in high dimension, but adopt a different perspective: rather than modifying the cost function, we return to the more fundamental view of Monge and propose to use Brenier's theorem and Caffarelli's regularity theory to define a new procedure for estimating lipschitzian transport maps which are the gradient of a strongly convex function.

Continuous-depth neural networks can be viewed as deep limits of discrete neural networks whose dynamics resemble a discretization of an ordinary differential equation (ODE). Although important steps have been taken to realize the advantages of such continuous formulations, most current techniques are not truly continuous-depth as they assume identical layers. Indeed, existing works throw into relief the myriad difficulties presented by an infinite-dimensional parameter space in learning a continuous-depth neural ODE. To this end, we introduce a shooting formulation which shifts the perspective from parameterizing a network layer-by-layer to parameterizing over optimal networks described only by a set of initial conditions. For scalability, we propose a novel particle-ensemble parametrization which fully specifies the optimal weight trajectory of the continuous-depth neural network. Our experiments show that our particle-ensemble shooting formulation can achieve competitive performance, especially on long-range forecasting tasks. Finally, though the current work is inspired by continuous-depth neural networks, the particle-ensemble shooting formulation also applies to discrete-time networks and may lead to a new fertile area of research in deep learning parametrization.

No summary available.

Topological data analysis (TDA) extracts rich information from structured data (such as graphs or time series) present in modern learning problems. It will represent this information in the form of descriptors of which persistence diagrams are part, which can be described as point measures supported on a half-plane. Although they are not simple vectors, persistence diagrams can nevertheless be compared with each other using partial matching metrics. The similarity between these metrics and the usual metrics of optimal transport - another field of mathematics - has been known for a long time, but a formal link between these two fields remained to be established. The purpose of this thesis is to clarifier this connection so that we can use the many achievements of optimal transport afin developing new statistical tools (both theoretical and practical) for manipulating persistence diagrams. First, we show how partial optimal transport with boundary, a variant of classical optimal transport, provides us with a formalism that contains the usual DTA metrics. We then illustrate the beneficial contributions of this reformulation in different situations: a theoretical study and algorithm for effictively estimating the barycenters of persistence diagrams using regularized transport, characterization of continuous linear representations of the diagrams and their learning via a versatile neural network, as well as a stability result for linear averages of randomly drawn diagrams.

No summary available.

The squared Wasserstein distance is a natural quantity to compare probability distributions in a non-parametric setting. This quantity is usually estimated with the plug-in estimator, defined via a discrete optimal transport problem. It can be solved to $\epsilon$-accuracy by adding an entropic regularization of order $\epsilon$ and using for instance Sinkhorn's algorithm. In this work, we propose instead to estimate it with the Sinkhorn divergence, which is also built on entropic regularization but includes debiasing terms. We show that, for smooth densities, this estimator has a comparable sample complexity but allows higher regularization levels, of order $\epsilon^{1/2}$ , which leads to improved computational complexity bounds and a strong speedup in practice. Our theoretical analysis covers the case of both randomly sampled densities and deterministic discretizations on uniform grids. We also propose and analyze an estimator based on Richardson extrapolation of the Sinkhorn divergence which enjoys improved statistical and computational efficiency guarantees, under a condition on the regularity of the approximation error, which is in particular satisfied for Gaussian densities. We finally demonstrate the efficiency of the proposed estimators with numerical experiments.

In this article, we show how to embed the so-called CH2 equations into the geodesic flow of the Hdiv metric in 2D, which, itself, can be embedded in the incompressible Euler equation of a non compact Riemannian manifold. The method consists in embedding the incompressible Euler equation with a potential term coming from classical mechanics into incompressible Euler of a manifold and seeing the CH2 equation as a particular case of such fluid dynamic equation.

In this note, we propose a variational framework in which the minimization of the acceleration on the group of diffeomorphisms endowed with a right-invariant metric is well-posed. It relies on constraining the acceleration to belong to a Sobolev space of higher-order than the order of the metric in order to gain compactness. It provides the theoretical guarantee of existence of minimizers which is compulsory for numerical simulations.

On the space of probability densities, we extend the Wasserstein geodesics to the case of higher-order interpolation such as cubic spline interpolation. After presenting the natural extension of cubic splines to the Wasserstein space, we propose a simpler approach based on the relaxation of the variational problem on the path space. We explore two different numerical approaches, one based on multi-marginal optimal transport and entropic regularization and the other based on semi-discrete optimal transport.

No summary available.

These notes contains the material that I presented to the CEA-EDF-INRIA summer school about numerical optimal transport. These notes are, on purpose, written at an elementary level, with almost no prerequisite knowledge and the writing style is relatively informal. All the methods presented hereafter rely on convex optimization, so we start with a fairly basic introduction to convex analysis and optimization. Then, we present the entropic regularization of the Kantorovich formulation and present the now well known Sinkhorn algorithm, whose convergence is proven in continuous setting with a simple proof. We prove the linear convergence rate of this algorithm with respect to the Hilbert metric. The second numerical method we present use the dynamical formulation of optimal transport proposed by Benamou and Brenier which is solvable via non-smooth convex optimization methods. We end this short course with an overview of other dynamical formulations of optimal transport like problems.

We study the geodesic problem on the group of diffeomorphism of a domain M⊂Rd, equipped with the H(div) metric. The geodesic equations coincide with the Camassa-Holm equation when d=1, and represent one of its possible multi-dimensional generalizations when d>1. We propose a relaxation à la Brenier of this problem, in which solutions are represented as probability measures on the space of continuous paths on the cone over M. We use this relaxation to prove that smooth H(div) geodesics are globally length minimizing for short times. We also prove that there exists a unique pressure field associated to solutions of our relaxation. Finally, we propose a numerical scheme to construct generalized solutions on the cone and present some numerical results illustrating the relation between the generalized Camassa-Holm and incompressible Euler solutions.

We consider the group of smooth increasing diffeomorphisms Diff on the unit interval endowed with the right-invariant $H^1$ metric. We compute the metric completion of this space which appears to be the space of increasing maps of the unit interval with boundary conditions at $0$ and $1$. We compute the lower-semicontinuous envelope associated with the length minimizing geodesic variational problem. We discuss the Eulerian and Lagrangian formulation of this relaxation and we show that smooth solutions of the EPDiff equation are length minimizing for short times.

We study the geodesic problem on the group of diffeomorphism of a domain M⊂Rd, equipped with the H(div) metric. The geodesic equations coincide with the Camassa-Holm equation when d=1, and represent one of its possible multi-dimensional generalizations when d>1. We propose a relaxation à la Brenier of this problem, in which solutions are represented as probability measures on the space of continuous paths on the cone over M. We use this relaxation to prove that smooth H(div) geodesics are globally length minimizing for short times. We also prove that there exists a unique pressure field associated to solutions of our relaxation. Finally, we propose a numerical scheme to construct generalized solutions on the cone and present some numerical results illustrating the relation between the generalized Camassa-Holm and incompressible Euler solutions.

No summary available.

In this article, we show how to embed the so-called CH2 equations into the geodesic flow of the Hdiv metric in 2D, which, itself, can be embedded in the incompressible Euler equation of a non compact Riemannian manifold. The method consists in embedding the incompressible Euler equation with a potential term coming from classical mechanics into incompressible Euler of a manifold and seeing the CH2 equation as a particular case of such fluid dynamic equation.

No summary available.

The group of diffeomorphisms of a compact manifold endowed with the L^2 metric acting on the space of probability densities gives a unifying framework for the incompressible Euler equation and the theory of optimal mass transport. Recently, several authors have extended optimal transport to the space of positive Radon measures where the Wasserstein-Fisher-Rao distance is a natural extension of the classical L^2-Wasserstein distance. In this paper, we show a similar relation between this unbalanced optimal transport problem and the Hdiv right-invariant metric on the group of diffeomorphisms, which corresponds to the Camassa-Holm (CH) equation in one dimension. On the optimal transport side, we prove a polar factorization theorem on the automorphism group of half-densities. Geometrically, our point of view provides an isometric embedding of the group of diffeomorphisms endowed with this right-invariant metric in the automorphisms group of the fiber bundle of half densities endowed with an L^2 type of cone metric. This leads to a new formulation of the (generalized) CH equation as a geodesic equation on an isotropy subgroup of this automorphisms group. On S1, solutions to the standard CH thus give particular solutions of the incompressible Euler equation on a group of homeomorphisms of R^2 which preserve a radial density that has a singularity at 0. An other application consists in proving that smooth solutions of the Euler-Arnold equation for the Hdiv right-invariant metric are length minimizing geodesics for sufficiently short times.

Comparing probability distributions is a fundamental problem in data sciences. Simple norms and divergences such as the total variation and the relative entropy only compare densities in a point-wise manner and fail to capture the geometric nature of the problem. In sharp contrast, Maximum Mean Discrepancies (MMD) and Optimal Transport distances (OT) are two classes of distances between measures that take into account the geometry of the underlying space and metrize the convergence in law. This paper studies the Sinkhorn divergences, a family of geometric divergences that interpolates between MMD and OT. Relying on a new notion of geometric entropy, we provide theoretical guarantees for these divergences: positivity, convexity and metrization of the convergence in law. On the practical side, we detail a numerical scheme that enables the large scale application of these divergences for machine learning: on the GPU, gradients of the Sinkhorn loss can be computed for batches of a million samples.

On the space of probability densities, we extend the Wasserstein geodesics to the case of higher-order interpolation such as cubic spline interpolation. After presenting the natural extension of cubic splines to the Wasserstein space, we propose a simpler approach based on the relaxation of the variational problem on the path space. We explore two different numerical approaches, one based on multi-marginal optimal transport and entropic regularization and the other based on semi-discrete optimal transport.

The group of diffeomorphisms of a compact manifold endowed with the L^2 metric acting on the space of probability densities gives a unifying framework for the incompressible Euler equation and the theory of optimal mass transport. Recently, several authors have extended optimal transport to the space of positive Radon measures where the Wasserstein-Fisher-Rao distance is a natural extension of the classical L^2-Wasserstein distance. In this paper, we show a similar relation between this unbalanced optimal transport problem and the Hdiv right-invariant metric on the group of diffeomorphisms, which corresponds to the Camassa-Holm (CH) equation in one dimension. On the optimal transport side, we prove a polar factorization theorem on the automorphism group of half-densities. Geometrically, our point of view provides an isometric embedding of the group of diffeomorphisms endowed with this right-invariant metric in the automorphisms group of the fiber bundle of half densities endowed with an L^2 type of cone metric. This leads to a new formulation of the (generalized) CH equation as a geodesic equation on an isotropy subgroup of this automorphisms group. On S1, solutions to the standard CH thus give particular solutions of the incompressible Euler equation on a group of homeomorphisms of R^2 which preserve a radial density that has a singularity at 0. An other application consists in proving that smooth solutions of the Euler-Arnold equation for the Hdiv right-invariant metric are length minimizing geodesics for sufficiently short times.

In this note, we propose a variational framework in which the minimization of the acceleration on the group of diffeomorphisms endowed with a right-invariant metric is well-posed. It relies on constraining the acceleration to belong to a Sobolev space of higher-order than the order of the metric in order to gain compactness. It provides the theoretical guarantee of existence of minimizers which is compulsory for numerical simulations.

This paper introduces the use of unbalanced optimal transport methods as a similarity measure for diffeomorphic matching of imaging data. The similarity measure is a key object in diffeomorphic registration methods that, together with the regularization on the deformation, defines the optimal deformation. Most often, these similarity measures are local or non local but simple enough to be computationally fast. We build on recent theoretical and numerical advances in optimal transport to propose fast and global similarity measures that can be used on surfaces or volumetric imaging data. This new similarity measure is computed using a fast generalized Sinkhorn algorithm. We apply this new metric in the LDDMM framework on synthetic and real data, fibres bundles and surfaces and show that better matching results are obtained.

No summary available.

This paper introduces the use of unbalanced optimal transport methods as a similarity measure for diffeomorphic matching of imaging data. The similarity measure is a key object in diffeomorphic registration methods that, together with the regularization on the deformation, defines the optimal deformation. Most often, these similarity measures are local or non local but simple enough to be computationally fast. We build on recent theoretical and numerical advances in optimal transport to propose fast and global similarity measures that can be used on surfaces or volumetric imaging data. This new similarity measure is computed using a fast generalized Sinkhorn algorithm. We apply this new metric in the LDDMM framework on synthetic and real data, fibres bundles and surfaces and show that better matching results are obtained.

No summary available.

We study a second-order variational problem on the group of diffeomorphisms of the interval [0, 1] endowed with a right-invariant Sobolev metric of order 2, which consists in the minimization of the acceleration. We compute the relaxation of the problem which involves the so-called Fisher-Rao functional a convex functional on the space of measures. This relaxation enables the derivation of several optimality conditions and, in particular, a sufficient condition which guarantees that a given path of the initial problem is also a minimizer of the relaxed one. This sufficient condition is related to the existence of a solution to a Riccati equation involving the path acceleration.

No summary available.

We study completeness properties of the Sobolev diffeomorphism groups Ds(M) endowed with strong right-invariant Riemannian metrics when the underlying manifold M is ℝd or compact without boundary. The main result is that for dim M/2 + 1, the group Ds (M) is geodesically and metrically complete with a surjective exponential map. We also extend the result to its closed subgroups, in particular the group of volume preserving diffeomorphisms and the group of symplectomorphisms. We then present the connection between the Sobolev diffeomorphism group and the large deformation matching framework in order to apply our results to diffeomorphic image matching.

This paper introduces a novel steepest descent flow in Banach spaces. This extends previous works on generalized gradient descent, notably the work of Charpiat et al., to the setting of Finsler metrics. Such a generalized gradient allows one to take into account a prior on deformations (e.g., piecewise rigid) in order to favor some specific evolutions. We define a Finsler gradient descent method to minimize a functional defined on a Banach space and we prove a convergence theorem for such a method. In particular, we show that the use of non-Hilbertian norms on Banach spaces is useful to study non-convex optimization problems where the geometry of the space might play a crucial role to avoid poor local minima. We show some applications to the curve matching problem. In particular, we characterize piecewise rigid deformations on the space of curves and we study several models to perform piecewise rigid evolution of curves.

This paper develops a method for higher order parametric regression on diffeomorphisms for image regression. We present a principled way to define curves with nonzero acceleration and nonzero jerk. This work extends methods based on geodesics which have been developed during the last decade for computational anatomy in the large deformation diffeomorphic image analysis framework. In contrast to previously proposed methods to capture image changes over time, such as geodesic regression, the proposed method can capture more complex spatio-temporal deformations. We take a variational approach that is governed by an underlying energy formulation, which respects the nonflat geometry of diffeomorphisms. Such an approach of minimal energy curve estimation also provides a physical analogy to particle motion under a varying force field. This gives rise to the notion of the quadratic, the cubic and the piecewise cubic splines on the manifold of diffeomorphisms. The variational formulation of splines also allows for the use of temporal control points to control spline behavior. This necessitates the development of a shooting formulation for splines. The initial conditions of our proposed shooting polynomial paths in diffeomorphisms are analogous to the Euclidean polynomial coefficients. We experimentally demonstrate the effectiveness of using the parametric curves both for synthesizing polynomial paths and for regression of imaging data. The performance of the method is compared to geodesic regression.

This article presents a new class of "optimal transportation"-like distances between arbitrary positive Radon measures. These distances are defined by two equivalent alternative formulations: (i) a "fluid dynamic" formulation defining the distance as a geodesic distance over the space of measures (ii) a static "Kantorovich" formulation where the distance is the minimum of an optimization program over pairs of couplings describing the transfer (transport, creation and destruction) of mass between two measures. Both formulations are convex optimization problems, and the ability to switch from one to the other depending on the targeted application is a crucial property of our models. Of particular interest is the Wasserstein-Fisher-Rao metric recently introduced independently by [CSPV15,KMV15]. Defined initially through a dynamic formulation, it belongs to this class of metrics and hence automatically benefits from a static Kantorovich formulation. Switching from the initial Eulerian expression of this metric to a Lagrangian point of view provides the generalization of Otto's Riemannian submersion to this new setting, where the group of diffeomorphisms is replaced by a semi-direct product of group. This Riemannian submersion enables a formal computation of the sectional curvature of the space of densities and the formulation of an equivalent Monge problem.

The geometric approach to diffeomorphic image registration known as large deformation by diffeomorphic metric mapping (LDDMM) is based on a left action of diffeomorphisms on images, and a right-invariant metric on a diffeomorphism group, usually defined using a reproducing kernel. We explore the use of left-invariant metrics on diffeomorphism groups, based on reproducing kernels defined in the body coordinates of a source image. This perspective, which we call Left-LDM, allows us to consider non-isotropic spatially-varying kernels, which can be interpreted as describing variable deformability of the source image. We also show a simple relationship between LDDMM and the new approach, implying that spatially-varying kernels are interpretable in the same way in LDDMM. We conclude with a discussion of a class of kernels that enforce a soft mirror-symmetry constraint, which we validate in numerical experiments on a model of a lesioned brain.

This paper studies the space of $BV^2$ planar curves endowed with the $BV^2$ Finsler metric over its tangent space of displacement vector fields. Such a space is of interest for applications in image processing and computer vision because it enables piecewise regular curves that undergo piecewise regular deformations, such as articulations. The main contribution of this paper is the proof of the existence of a shortest path between any two $BV^2$ curves for this Finsler metric. % The method of proof relies on the construction of a martingale on a space satisfying the Radon-Nikodym property and on the invariance under reparametrization of the Finsler metric. This method applies more generally to similar cases such as the space of curves with $H^k$ metrics for $k\geq 2$ integer. When $k \geq 2$ is integer, this space has a strong Riemannian structure and is geodesically complete. Thus, our result shows that the exponential map is surjective, which is complementary to geodesic completeness in infinite dimensions. We propose a finite element discretization of the minimal geodesic problem, and use a gradient descent method to compute a stationary point of a regularized energy. Numerical illustrations shows the qualitative difference between $BV^2$ and $H^2$ geodesics.

The geometric approach to diffeomorphic image registration known as "large deformation by diffeomorphic metric mapping" (LDDMM) is based on a left action of diffeomorphisms on images, and a right-invariant metric on a diffeomorphism group, usually defined using a reproducing kernel. We explore the use of left-invariant metrics on diffeomorphism groups, based on reproducing kernels defined in the body coordinates of a source image. This perspective, which we call Left-LDM, allows us to consider non-isotropic spatially-varying kernels, which can be interpreted as describing variable deformability of the source image. We also show a simple relationship between LDDMM and the new approach, implying that spatially-varying kernels are interpretable in the same way in LDDMM. We conclude with a discussion of a class of kernels that enforce a soft mirror-symmetry constraint, which we validate in numerical experiments on a model of a lesioned brain.

The workshop “Math in the cabin” took place in Bad Gastein, in the period July 16 – July 22, 2014. The aim of the week was to bring together a group of researchers with diverse backgrounds — ranging from differential geometry to applied medical image analysis — to discuss questions of common interest, that can be vaguely summarized under the heading “shape analysis”. These proceedings contain a summary of selected discussions, that were held during this week.

In the context of Alzheimer's disease, two challenging issues are (1) the characterization of local hippocampal shape changes specific to disease progression and (2) the identification of mild-cognitive impairment patients likely to convert. In the literature, (1) is usually solved first to detect areas potentially related to the disease. These areas are then considered as an input to solve (2). As an alternative to this sequential strategy, we investigate the use of a classification model using logistic regression to address both issues (1) and (2) simultaneously. The classification of the patients therefore does not require any a priori definition of the most representative hippocampal areas potentially related to the disease, as they are automatically detected. We first quantify deformations of patients' hippocampi between two time points using the large deformations by diffeomorphisms framework and transport these deformations to a common template. Since the deformations are expected to be spatially structured, we perform classification combining logistic loss and spatial regularization techniques, which have not been explored so far in this context, as far as we know. The main contribution of this paper is the comparison of regularization techniques enforcing the coefficient maps to be spatially smooth (Sobolev), piecewise constant (total variation) or sparse (fused LASSO) with standard regularization techniques which do not take into account the spatial structure (LASSO, ridge and ElasticNet). On a dataset of 103 patients out of ADNI, the techniques using spatial regularizations lead to the best classification rates. They also find coherent areas related to the disease progression.

No summary available.

No summary available.

This paper introduces a variational strategy to learn spatially-varying metrics on large groups of images, in the Large Deformation Diffeomorphic Metric Mapping (LDDMM) framework. Spatially-varying metrics we learn not only favor local deformations but also correlated deformations in different image regions and in different directions. In addition, metric parameters can be efficiently estimated using a gradient descent method. We first describe the general strategy and then show how to use it on 3D medical images with reasonable computational ressources. Our method is assessed on the 3D brain images of the LPBA40 dataset. Results are compared with ANTS-SyN and LDDMM with spatially-homogeneous metrics.

Motivated by the development of a probabilistic model for growth of biological shapes in the context of large deformations by diffeomorphisms, we present a stochastic perturbation of the Hamiltonian equations of geodesics on shape spaces. We study the finite-dimensional case of groups of points for which we prove that the strong solutions of the stochastic system exist for all time. We extend the model to the space of parameterized curves and surfaces and we develop a convenient analytical setting to prove a strong convergence result from the finite-dimensional to the infinite-dimensional case. We then present some enhancements of the model.

We present a new framework for diffeomorphic image registration which supports natural interpretations of spatially-varying metrics. This framework is based on left-invariant diffeomorphic metrics (LIDM) and is closely related to the now standard large deformation diffeomorphic metric mapping (LDDMM). We discuss the relationship between LIDM and LDDMM and introduce a computationally convenient class of spatially-varying metrics appropriate for both frameworks. Finally, we demonstrate the effectiveness of our method on a 2D toy example and on the 40 3D brain images of the LPBA40 dataset.

In this paper, we propose a new strategy for modelling sliding conditions when registering 3D images in a piecewise-diffeomorphic framework. More specifically, our main contribution is the development of a mathematical formalism to perform Large Deformation Diffeomorphic Metric Mapping registration with sliding conditions. We also show how to adapt this formalism to the LogDemons diffeomorphic registration framework. We finally show how to apply this strategy to estimate the respiratory motion between 3D CT pulmonary images. Quantitative tests are performed on 2D and 3D synthetic images, as well as on real 3D lung images from the MICCAI EMPIRE10 challenge. Results show that our strategy estimates accurate mappings of entire 3D thoracic image volumes that exhibit a sliding motion, as opposed to conventional registration methods which are not capable of capturing discontinuous deformations at the thoracic cage boundary. They also show that although the deformations are not smooth across the location of sliding conditions, they are almost always invertible in the whole image domain. This would be helpful for radiotherapy planning and delivery.

This thesis takes place in the context of image matching within the framework of large deformation diffeomorphisms. With important applications to medical imaging and computational anatomy, this approach uses the action of diffeomorphisms groups in order to classify images. One of the first issue to deal with is to compute the distance between objects on which can act the group of diffeomorphisms. The case of discontinuous images was very partially understood. The first part of this thesis is devoted to fully tackle the case of discontinuous images in any dimension. Namely the images are assumed to be functions of bounded variations. We have provided technical tools to deal with discontinuous images within the diffeomorphism framework. The first application developed is a Hamiltonian formulation of the geodesic equations for a new model including a change of contrast in the images which is represented by an action of a diffeomorphism on the values of the level lines of the image. The second one is an extension of the metamorphosis framework developed by A.