Guillaume Carlier

Alfred Galichon

Filippo Santambrogio

François Pitié

Anil C Kokaram

Rozenn Dahyot

Jean-David Benamou

José A Carillo

Maxime Gheysens

Arthur Leclaire

Méthodes unidimensionnelles et d'évolution pour le transport optimal

Sur une droite, le transport optimal ne pose pas de dicultés. Récemment, ce constat a été utilisé pour traiter des problèmes plus généraux. En eet, on a remarqué qu'une habile désintégration permet souvent de se ramener à la dimension un, ce qui permet d'utiliser les méthodes aérentes pour obtenir un premier résultat, que l'on fait ensuite évoluer pour gagner en précision [, , ].

Je montre ici l'ecacité de cette approche, en revenant sur deux problèmes déjà résolus partiellement de cette manière, et en complétant la réponse qui en avait été donnée.

Le premier problème concerne le calcul de l'application de Yann Brenier. En eet, Guillaume Carlier, Alfred Galichon et Filippo Santambrogio [] ont prouvé que celle-ci peut être obtenue grâce à une équation diérentielle, pour laquelle une condition initiale est donnée par le réarrangement de Knothe-Rosenblatt (lui-même déni via une succession de transformations unidimensionnelles). Ils n'ont cependant traité que des mesures nales discrètes ; j'étends leur résultat aux cas continus []. L'équation de Monge-Ampère, une fois dérivée, donne une pour le potentiel de Kantorovitch ; mais pour obtenir une condition initiale, il faut utiliser le théorème des fonctions implicites de Nash-Moser.

Le chapitre rappelle quelques résultats essentiels de la théorie du transport optimal, et le chapitre est consacré au théorème de Nash-Moser. J'expose ensuite mes propres résultats dans le chapitre , et leur implémentation numérique dans le chapitre .

Enn, le dernier chapitre est consacré à l'algorithme , développé par François Pitié, Anil C. Kokaram et Rozenn Dahyot []. Celui-ci construit une application de transport susamment proche de celle de M. Brenier pour convenir à la plupart des applications []. Une interprétation en est proposée en termes de ot de gradients dans l'espace des probabilités, avec pour fonctionnelle la distance de Wasserstein projetée. Je démontre aussi l'équivalence de celle-ci avec la distance usuelle de Wasserstein.

Unidimensional and Evolution Methods for Optimal Transportation

In dimension one, optimal transportation is rather straightforward. The easiness with which a solution can be obtained in that setting has recently been used to tackle more general situations, each time thanks to the same method [, , ]. First, disintegrate your problem to go back to the unidimensional case, and apply the available methods to get a rst result; then, improve it gradually using some evolution process.

This dissertation explores that direction more thoroughly. Looking back at two problems only partially solved this way, I show how this viewpoint in fact allows to go even further.

The rst of these two problems concerns the computation of Yann Brenier's optimal map. Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio [] found a new way to obtain it, thanks to an dierential equation for which an initial condition is given by the Knothe-Rosenblatt rearrangement. (The latter is precisely dened by a series of unidimensional transformations.) However, they only dealt with discrete target measures; I generalize their approach to a continuous setting []. By dierentiation, the Monge-Ampère equation readily gives a satised by the Kantorovich potential; but to get a proper initial condition, it is necessary to use the Nash-Moser version of the implicit function theorem.

The basics of optimal transport are recalled in the rst chapter, and the Nash-Moser theory is exposed in chapter . My results are presented in chapter , and numerical experiments in chapter .

The last chapter deals with the algorithm, devised by François Pitié, Anil C. Kokaram, and Rozenn Dahyot []. It builds a transport map that seems close enough to the optimal map for most applications []. A complete mathematical understanding of the procedure is, however, still lacking. An interpretation as a gradient ow in the space of probability measures is proposed, with the sliced Wasserstein distance as the functional. I also prove the equivalence between the sliced and usual Wasserstein distances.

Introduction

Preface

How I learned of optimal transportation is a bit fortuitous. From time to time, a mathematical education can seem a bit lifeless; at least for me, it felt that way at some point during my scholarship at the École normale supérieure. Yet when I complained to Guillaume Carlier, who was my tuteur there, he suggested I should try a new subject: optimal transportation. As it was rooted in a very simple question-roughly, how to move stu eciently?-but still involved nice mathematics, he thought it might catch my interest. And it did.

Following his advice, I attended a series of lectures on the subject by François Bolley, Bruno Nazaret, and Filippo Santambrogio-which turned out to be very lively indeed. A year later, in , I was lucky enough to go to the Scuola Normale Superiore in Pisa to write my master thesis under the supervision of Luigi Ambrosio. I was to study one of the most abstract outcome of the theory: gradient ows in the space of probability measures. The months I spent there were intense, and exciting. I was therefore very glad to be able to start a h under the joint supervision of Professors Ambrosio and Santambrogio.

Over the three years that followed, I came to learn a lot, and not only about mathematics, but also about perseverance and self-organization, about trust in others' insights as well as in my own intuition-and about a researcher's life and my own aspirations. Of course, going back twice in Pisa for an extended amount of time, I also had the opportunity to learn more about Italy, its language, its culture, and its people.

It was a wonderful experience, for which I am immensely grateful.

-Communay, August ,

Introduction

Many illustrations can be found in the literature that try to simply present the problem lying at the heart of optimal transportation. Some talk, for instance, of sand piles to be moved [, ], or bread to be sent from bakeries to local cafés [], or coal to be delivered from mines to steelworks []. Let me indulge, however, in giving another example. Readers already familiar with the subject might be excused for skipping the following part; it should get more interesting afterwards.

Imagine you are the head of an industrial complex somewhere in China, maybe producing electronic components for a company called Appell Inc. The labor comes from rural areas all over the country, and needs housing close to the factories; therefore, the complex not only includes many plants, but also dormitories. Your task is to assign to each and every one of your workers a bed. But their commuting costs you money, as you have to pay for buses (or any other transportation system), and you want to minimize your expenses. How would you achieve it?

Assuming there is barely enough accommodation for everyone, we can represent the distributions of workers and beds by two measures µ and ν with the same total mass. Then, given an area A, the values µ (A) and ν (A) respectively indicate the numbers of employees and beds in that area. We will denote by c (x , ) the daily cost of transportation between the factory x and the dormitory , back and forth.

Since there are so many workers-that is, so many variables-, you cannot expect to nd a precise solution for everyone, but you need to operate from a "mesoscopic" level. A way to ease the search for a solution is to group your workers by factories, and try to send all the people working at the same place x to sleep in the same dormitory . In that case, what you are looking for is a mapping, = T (x ), telling you, for each factory, where to house its sta-that is, you want to nd a map T that minimizes the total cost of transportation, c (x , T (x )) dµ (x ),

and such that ν (A) = µ (T -(A)) for any area A, because T -(A) is where people sleeping in A come from. This version of the problem was historically the rst to be studied, by Gaspard Monge [] in the th century-although in term of sand particles rather than workers-, and has therefore come to be known as Monge's problem.

However, there might be no such mapping-for instance, if you have no choice but to split the workforce of a given factory between many dormitories. Hence, in the s, Leonid Kantorovich [, ] proposed instead to model a solution as a measure γ , such that γ (A × B) represents the number of people working in the area A and sleeping somewhere in B (this implies its marginals should be µ and ν ). The total cost of transportation for the plan γ is then given by c (x , ) dγ (x , ).

To nd an optimal γ is today called the Monge-Kantorovich problem; it really is a generalization of Monge's initial question, for if there is an optimal mapping T , then it corresponds to an optimal measure γ such that

γ (A × B) = µ (A ∩ T -(B)),
and the transport costs are the same.

In his papers, Kantorovich also showed you might be able-to keep our story going-to pass on the problem to the workers: just start charging for the accommodation, introduce fares to the transportation system to cover for its operation, and generously hand over a subsidy to compensate for all that. Indeed, values may exist for the subsidies and the bed rates such that the only solution for any employee not to lose money is to nd the right spot to sleep. That is, if S (x ) is the additional money you grant daily to the people working in the factory x, and B() is the price you ask for a bed in the dormitory , then you could perhaps manage to set S and B in such a way that S (x ) ≤ B() + c (x , ), with the double assurance that: () for any given x, there is equality for some 's; () if the workers in x comply and go to one of those 's, everyone may have a bed. In the end, you pay the dierence between what you hand over and what you get back from the accommodation fares, and if S and B are correctly set, that should be S (x ) dµ (x ) -B() dν () = min γ c (x , ) dγ (x , ).

The Monge-Kantorovich would then be solved, in some sense-but the diculty now lies in setting the right values for S and B. Those are called, when optimal, Kantorovich potentials. With Kantorovich's approach, you might have therefore to split a group of coworkers. On the other hand, if the factories are quite small, and not too concentrated, then there are not that many people working at the same place, so it should be easier to assign the same dormitory to them all: the solution might still be a mapping. For a cost equal to the squared distance, this was formally proved by Yann Brenier [, ] in the s, who also showed optimal values exist for the bed rates B and the subsidies S that force the employees to nd the right spot, which they do by simply following the direction of decreasing subsidies-more precisely, from a factory x, one should go to = T (x ) = x -∇S (x ). This was to be expected somehow, as the handouts should be fewer where there are more beds nearby.

But then, in practical terms, how to compute the optimal mapping T ? When both measures are discrete-that is, when the factories and the dormitories are scattered-, linear programming provides a solution, as does Dimitri P. Bertsekas's algorithm [].

However, when the distributions are more diuse, the problem is in general hard to solve-except in dimension one. In that case, there is a formula, which translates into the following method: if the factories and the dormitories are all aligned along the same street, you should do the assignment going from one end to the other, and allocate the rst bed you encounter to the rst man you meet, and so on. In other terms, if F and G stand for the cumulative distributions of the workers and beds-that is, if F (t ) and G (t ) are respectively the total numbers of workers and

f T x F (x )
G () beds located before the point t-, then people working in x should go to sleep to = T (x ) = G -• F (x ); see gure A, on this page.

F (x ) G ()
In greater dimensions, even if many numerical methods have been developed [, , , , , ], the problem remains dicult. It is, for instance, possible to start from a non-optimal mapping, like the Knothe-Rosenblatt rearrangement-which, as we shall see, applies the previous formula on each dimension-, and then alter it through a steepest-descent algorithm so as to make it optimal []. Or, using the peculiar form the optimal map should have, T (x ) = x -∇S (x ), one can start from a non-optimal potential S , and then apply Newton's method to catch the optimal S []. By some aspects, my paper [] combines these two approaches, since it computes the optimal potential S rather than the map T directly, but it nevertheless manages to start from Knothe's map. (I will present the results of this paper in chapter , with new numerical experiments in chapter ).

This Knothe-Rosenblatt rearrangement was devised independently by Herbert

Knothe [] and Murray Rosenblatt [] in the s. It is a mapping, assigning to each worker from your industrial complex a bed in a dormitory-although, a priori, not in a very cost-eective way-by solving the problem on each dimension one after the other, thanks to the unidimensional solution to Monge's problem. Let us assume the measures µ and ν have densities, which we denote by f and ; then f (x ) is the number of workers in the factory x, and () is the number of beds in the dormitory .

If the complex's roads are divided into avenues (north-south) and streets (west-east), then the position x = (x , x ) of a factory is given by the intersection of an avenue x and a street x ; the same for a dormitory's position = ( , ). To assign the beds, we can start by summing up the workforces on each avenue on the one hand, and the beds on the other hand:

f (x ) = f (x , x ) dx , (x ) = ( , ) d .
We denote by F and Ĝ the cumulative distributions of f and . Then, dealing with each avenue from the west to the east, one after the other, we tell the workers on the avenue x to look for a dormitory on the most western avenue with some spare capacity-and this avenue will be = T K (x ) = Ĝ -• F (x ). Once everybody has a designated avenue where to nd a bed, we proceed likewise to assign a street, and its intersection with the avenue will yield the dormitory's position: starting from the north and moving southward, we tell people working in x = (x , x ) to go to the most northern dormitory they can nd on the avenue = T K (x ) with some beds left, which will be at the intersection with the street = T K (x , x ) = Ĝ -• Fx (x ), with Fx and Ĝ the (normalized) cumulative distributions of workers and beds on the avenues x and respectively. The Knothe-Rosenblatt rearrangement is the mapping we thus obtain, T K = (T K , T K ); see gure B, on the next page. Sadly, as this transport map deals with each dimension in a certain order, on which the result strongly depends, it is anisotropic, and thus unsuitable for many applications-e.g., in image processing-because it creates artifacts.

f x f T K f x x T K x T K
Figure B: Construction of the Knothe-Rosenblatt rearrangement ( , ) = T K (x , x ), dened by = T K (x ) and = T K (x , x ). For each dimension, the hashed zones have the same areas, respectively F (x ) = G ( ), and F

x (x ) = G ( ).

The starting point of the theory I will present in chapter is that this mapping would however be optimal, should the price of a north-south displacement be a lot less expensive than a weast-east one-i.e., the rearrangement would be optimal for a transportation cost c ε (x , ) = |x -| + ε |x -| , with ε innitesimally small. But, increasing ε little by little and updating the optimal mapping accordingly, we could get back the optimal map for a regular quadratic cost, at least if we can get to ε = . This was achieved by Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio [], under the assumption the target measure is discrete-that is, when the dormitories are scattered.

Pursuing their work, I was able to deal with more diuse distributions []. They had found a dierential equation satised by the Kantorovich potential S; I therefore sought to do the same. We have seen that, for a cost equal to the squared distance, c (x , ) = |x -| + |x -| , the optimal transport map is:

T (x ) = x -∇S (x ) = x -        ∂ S (x ) ∂ S (x )        .
But for a cost c ε (x , ) = |x -| + ε |x -| , the optimal map can be written as

T ε (x ) = x -        ∂ S ε (x ) ∂ S ε (x )/ε        = x -A - ε ∇S ε (x ) with A ε =        ε        .
Since T ε must still send the measure µ onto the measure ν , that is,

ν (A) = ∈A () d = T ε (x ) ∈A f (x ) dx = µ (T - ε (A))
for any area A, the following equality, called a Monge-Ampère equation, must always hold:

f (x ) = (T ε (x )) det(DT ε ) = (x -A - ε ∇S ε (x )) det(I d -A - ε ∇ S ε (x )). (a)
This equation, along with the further condition A ε -∇ S ε > (to force uniqueness), completely determines the potential S ε . The implicit function theorem then allows us to get information on its regularity in the following way: First, for u smooth enough such that A ε -∇ u > , we set

F (ε , u) := f -(Id -A - ε ∇u) det(I d -A - ε ∇ u),
so that F (ε , u) = if and only if u = S ε . Then, the dierential with respect to u, denoted by D u F, is a second-order, strictly elliptic dierential operator, which is invertible; hence, ε → S ε is at least C . Dierentiating the equation (a) with respect to ε, we therefore get a second-order, elliptic partial dierential equation:

div f I d -A - ε ∇ S ε - A - ε ∇ Ṡε -Ȧε A - ε ∇S ε = . (b)
The dotted symbols, Ṡε and Ȧε , represent the derivatives with respect to ε; the target density is here hidden in the determinant of I d -A - ε ∇ S ε . As long as ε stays away from zero, this last equation can be solved, and Ṡε is the unique solution. So, if we know S ε for some ε > , we can get S back, since we can obtain Ṡε by solving the elliptic equation (b), and then compute S = S ε + ε Ṡε dε. This is akin to the continuation method, which was used by Philippe Delanoë But what happens when ε is innitesimally small, and tends to zero? On the one hand, we know T ε converges to be the Knothe-Rosenblatt rearrangement,

= T K (x ) = (T K (x ), T K (x , x )).
On the other hand, when ε is innitesimally small but still nonzero,

= T ε (x ) = x -(∂ S ε (x ),∂ S ε (x )/ε ).
To reconcile this with the previous expression, and cancel the /ε, maybe we can

write S ε (x ) = S ε (x ) + εS ε (x , x ). Then, T ε (x ) = x -        ∂ S ε (x ) + ε∂ S ε (x , x ) ∂ S ε (x , x )        -→ ε→ x -        ∂ S (x ) ∂ S (x , x )        = T K (x ),
so this viewpoint covers the case ε = as well. This turns out to be the correct approach: in some sense, S ε and S ε are uniquely determined by their initial conditions S and S , which come from the Knothe rearrangement

T K = Id -(∂ S ,∂ S
). However, while the implicit function theorem was enough when ε stayed away from zero, results on the behavior of S ε = S ε + εS ε when ε goes to zero prove a lot more dicult to get. The rst idea that comes to mind is to try to apply the implicit function theorem once more, but this time to

G(ε , u , u ) := F (ε , u ε ) = f -(Id -A - ε ∇u ε ) det(I d -A - ε ∇ u ε ), dened for ε > , with u ε := u + εu ; when ε = , we can set G(, u , u ) := f -(Id -∂u) det(I d -∇∂u) where ∂u := (∂ u ,∂ u ).
The problem is, even though it is possible to solve

D (u ,u ) G(, S , S )( , ) = q,
for u , u ∈ C k+ and q ∈ C k , the best we can get for the solution ( ,

) is ∈ C k+ ,
which is good, and ∂ , ∈ C k , which is very bad: we need ∈ C k+ . There is, therefore, a loss of regularity, which prevents us from applying the implicit function theorem again. To get around such a diculty, a solution is to work with C ∞ maps, so as to have an innite source of smoothness. But then, we cannot use the implicit function theorem any longer, as C ∞ is not a Banach space; we need instead to use the stronger Nash-Moser theorem, which I will present in chapter .

After the theoretical aspects presented in chapter , I will show how this method can allow us eectively to compute Brenier's map for the regular quadratic cost, = T (x ), in chapter . The idea is the go backward, starting from ε = and going up to ε = . This numerical material is new, and was not present in my original paper []. It is, however, still sketchy: there is yet a considerable amount of work to be done in order to obtain something that can be used practically.

Finally, in the last chapter, a second problem, of a dierent kind, is introduced; it is however born out of the same overall approach. Since the optimal transport map is so easy to compute in dimension one, and so dicult to get in higher dimensions, the image processing community has devised a way to build another transport map, using only unidimensional mappings [, ]-not unlike Knothe's rearrangement therefore, but without its greatest aw, which is its being anisotropic. Experimentally, it works well enough. We can iterate the procedure, with µ instead of µ and using a dierent basis e, and thus get another map T e ; then we dene µ as the measure obtain from µ through the new T e , and start again. In the end, if all the bases are well chosen, no particular direction should be privileged, and µ n should converge toward ν. Notice that, at each µ n converges to ν , but it has not been proved yet-except in a very particular case, when the target measure ν is Gaussian. But even though the transport map between µ and µ n does not necessarily converge toward the optimal map between µ and ν , it has nevertheless been successfully used as a replacement [].

I will present in the last chapter some steps toward a more complete understanding. This algorithm seems to be connected to a gradient ow in the space of probability measures-in the sense of the theory developed by Luigi Ambrosio, Nicola

W p (µ, ν ) := min γ |x -| p dγ (x , ) /p .
Indeed if, instead of dening the transport map T between µ n and µ n+ by (c) with a random basis e, and hoping for the randomness to homogenize the procedure, we would rather dene T (x ) := T e (e |x) de;

then, assuming the measures are sums of N Dirac masses-and therefore assimilable to vectors of R d × N -, we obtain that the measure µ n+ is given by

µ n+ := µ n -∇F (µ n ) with F (µ) := SW (µ, ν ) .
This is nothing but the explicit Euler scheme for the gradient ow equation μt := -∇F (µ t ).

Following the variational method devised by Richard Jordan, David Kinderlehrer, and Felix Otto [], and investigated by Luigi Ambrosio, Nicola Gigli, and Giuseppe

Savaré [], we can dene an implicit Euler scheme,

µ n+ = µ n -h∇F (µ n+ ),
by taking

µ n+ ∈ arg min µ h W (µ n , µ) + SW (µ, ν ) .
The Wasserstein distance here replaces the usual Euclidean distance, which is used to dene the classical implicit scheme on R d . Notice this denition works even if the measures are no longer assumed to be discrete. In any case, the sequences (µ n ) n ∈N converge in some sense to a curve (µ t ) t ≥ when the time step tends to . This viewpoint could yield a theoretical justication of the algorithm, if we were able to prove the convergence of µ t toward ν when t tends to innity; to do so will, however, require more work still.

Chapter

Optimal transportation

... The aim of this chapter is to recall some well-known facts that shall be needed later on. The presentation has therefore been tailored with a further use in mind, and proofs are only given when they are either very short or of a special interest.

Notations are also set here.

For a general introduction to optimal transportation, the reader should rather refer to Cédric Villani's summae [, ] or Filippo Santambrogio's forthcoming The former condition, ν = T # µ, means that T should transport µ onto ν ; that is, ν should be the push-forward of µ by T : for any ξ , ξ () dν () = ξ (T (x )) dµ (x ). The latter asks the total cost of transportation to be minimal.

... Monge-Kantorovich problem. Depending on the measures, there might be no transport map sending µ onto ν , for instance if µ is discrete and ν is uniform.

Hence, the following generalization was proposed by Leonid Kantorovich [, ]: instead of looking for a mapping,

nd a measure γ ∈ Γ(µ, ν ) such that c (x , ) dγ (x , ) is minimal, (...a)
where Γ(µ, ν ) stands for the set of all transport plans between µ and ν , i.e. the probability measures on R d × R d with marginals µ and ν . This problem really extends Monge's, for any transport map T sending µ onto ν yields a measure γ ∈ Γ(µ, ν ),

which is γ = (Id, T ) # µ, i.e. the only measure γ on R d × R d such that ∀ ξ ∈ C b (R d × R d ), ξ (x , ) dγ (x , ) = ξ (x , T (x )) dµ (x ),
and the associated costs of transportation are the same. However, unlike in Monge's problem, for which there might be no admissible transport map-not to mention an optimal one-, in Kantorovich's version there is always a transport plan, for instance µ ⊗ ν . Even better, it is not dicult to show there is always a solution:

... Proof. On one hand, as µ and ν are inner regular, the set Γ(µ, ν ) is tight and thus, being obviously closed, compact according to Prokhorov's theorem. On the other hand, as c is lower semicontinuous, the map γ → c (x , ) dγ (x , ) is also lower semicontinuous; for if

c n (x , ) := inf x , c ( x , ) + n |x -x | + | -| , then c n is continuous, c n (x , ) ≤ c (x , )
, and c n converges pointwise to c, and this, as soon as

γ k → γ , implies c dγ ≤ lim inf n→∞ c n ∧ n dγ ≤ lim inf n→∞ lim inf k→∞ c n ∧ n dγ k ≤ lim inf k→∞ c dγ k
Thus, any minimizing sequence converges, up to an extraction, to a minimizer.

... Dual formulation. As will be shown in proposition .. on the following page, there is a form of duality between the Monge-Kantorovich problem and the following other problem:

nd ψ , φ ∈ C (R d ) such that ψ (x ) + φ() ≤ c (x , ) and ψ dµ + φ dν is maximal. (...a)
This is often called the dual or sometimes primal problem, because they are linked (see proposition .. on the next page), and the space of signed Radon measures-where the Monge-Kantorovich problem is dened-is the dual of the space of continuous functions vanishing at innity-where this new problem is dened, even though the condition to vanish at innity is irrelevant. Whatever the naming, the requirement

ψ , φ ∈ C (R d
) can be relaxed, so that (...a) becomes:

nd ψ ∈ L (µ), φ ∈ L (ν ) such that ψ (x ) + φ() ≤ c (x , )
φ() = inf x c (x , ) -ψ (x ) and ψ (x ) = inf c (x , ) -φ() .
The rst equality, when holding, will be written φ = ψ c , where ψ c is called the c-transform of ψ . Similarly, for the second we shall write ψ = φ c . If both are veriedthat is, if ψ = ψ cc -, then ψ is said to be c-concave. Then, the problem (...b) becomes

nd ψ ∈ L (µ) such that ψ dµ + ψ c dν is maximal. (...a)
Any solution ψ is called a Kantorovich potential between µ and ν .

... P. Let µ, ν be two Borel probability measures on

R d . If the cost function c : R d × R d → [, +∞) is lower semicontinuous and c (x , ) dµ (x ) dν () < ∞,
then there is a Borel map ψ : R d → R that is c-concave and optimal for (...a).

Moreover, the resulting maximum is equal to the minimum of the Monge-Kantorovich problem (...a):

min γ ∈Γ( µ ,ν ) c (x , ) dγ (x , ) = max φ ∈L ( µ) φ(x ) dµ (x ) + φ c () dν () . If γ ∈ Γ(µ, ν ) is optimal, then ψ (x ) + ψ c () = c (x ,
) almost everywhere for γ .

For a proof of this proposition, see the monograph by Luigi Ambrosio, Giuseppe Savaré, and Nicola Gigli [, Theorem ..].

. Solution on the real line ... Cumulative distribution and generalized inverse. If µ is a probability measure on R, its cumulative distribution is the map F : R → [, ] dened by

F (x ) := µ ((-∞, x]).
Its is an nondecreasing and right-continuous function. For such a map, it is possible to dene a generalized inverse F -, also called quantile function, by setting

F -() := min x ∈ [-∞, ∞]     ≤ F (x ) .
The values of F -give the dierent quantiles: for instance, F -(/) yields the third quartile-hence the alternate name.

... Lemma. If F is a cumulative distribution, then ≤ F (x ) if and only if F -() ≤

x.

Proof. Since the minimum in the denition of

F -is attained, ≤ F (F -()) for any . Thus, if F -() ≤ x for some x, then ≤ F (F -()) ≤ F (x ), as F is nondecreasing. Conversely, if ≤ F (x ), then the denition of F -implies F -() ≤ x.
... P. Let h ∈ C (R) be a nonnegative, strictly convex function. Let µ and ν be Borel probability measures on R such that

h(x -) dµ (x ) dν () < ∞. (...a)
If µ has no atom, and F and G stand for the respective cumulative distribution of µ and ν , then

T := G -• F solves Monge's problem for the cost c (x , ) = h(x -).
If γ is the induced transport plan, that is, γ := (Id, T ) # µ, then γ is optimal for the Monge-Kantorovich problem.

Proof. To begin with, notice T is well dened almost everywhere for µ. Indeed, there might be a problem only when

F (x ) = , for G -() = -∞. But F = only on (-∞, a]
for some a ∈ R, and, by the very denition of F , we have µ ((-∞, a]) = F (a) = .

Notice also that, as F and G are nondecreasing, T must be nondecreasing as well.

Then, lemma .. on this page applied to the cumulative distribution G yields

T -((-∞, ]) = x ∈ [-∞, +∞]      G -(F (x )) ≤ = x ∈ [-∞, +∞]     F (x ) ≤ G () .
First, this set has to be an interval, as T is nondecreasing. Second, since µ has no atom, F is increasing and continuous, so this interval must be closed. Thus, if x is its supremum, we must have F (x ) = G (), and therefore

µ (T -((-∞, ])) = µ ((-∞, x]) = F (x ) = G () = ν ((-∞, ]).
This is enough to show ν = T # µ.

Now, let us prove T is optimal. On the one hand, if u ≥ x, then, as T and h are nondecreasing, h (u -T (u)) ≤ h (u -T (x )). Integrating between x and some ≥ x, we get

x h (u -T (u)) du ≤ x h (u -T (x )) du ≤ h( -T (x )) -h(x -T (x )).
On the other hand, if u ≤ x, then h (u -T (u)) ≥ h (u -T (x )); integrating bewteen x and ≤ x, we again get

x h (u -T (u)) du ≤- x h (u -T (x )) du ≤ h( -T (x )) -h(x -T (x )).
Thus, if we set

ψ () := h (u -T (u)) du, then, in any case, ψ () -ψ (x ) ≤ h( -T (x )) -h(x -T (x )), which implies ψ c (T (x )) := inf h( -T (x )) -ψ () = h(x -T (x )) -ψ (x ),
and this yields ψ is c-concave. On the other hand, the condition (...a) ensures that there are x and such that h(x -) dµ (x ) < ∞ and h(x -) dν () < ∞.

Since h(x -)ψ c ( ) ≥ ψ (x ), and h(x -T (x ))ψ (x ) ≥ ψ c (T (x )), and also

ψ (x ) ≥-ψ c (T (x )), we have h(x -) -ψ c ( ) ≥ ψ (x ) ≥-h(x -T (x )) + ψ (x )
and as

T # µ = ν , this implies ψ ∈ L (µ). Similarly, ψ c ∈ L (ν ). Therefore, integrating the equality ψ (x ) + ψ c (x ) = h(x -T (x )) with respect to µ gives ψ (x ) dµ (x ) + ψ c () dν () = c (x , T (x )) dµ (x ).
Since ψ (x ) + ψ c () ≤ c (x , ) for all pair (x , ), if γ is any other transport plan, the associated total transport cost is necessarily greater, and thus T is optimal.

. Yann Brenier's map and its regularity For a strictly convex cost, however, things are somewhat easier. At the end of the s, Yann Brenier [, ] gave a general answer when the cost function is the squared Euclidean distance, and showed the key role convex functions play in that case. Since, his theorem has been extended to arbitrary, strictly convex cost functions, and for measures dened on a variety of domains; those cases will be studied in section . on page .

... Subdierential of a convex function. Let φ : R d → (-∞, +∞] be a convex, lower semicontinuous function. Then, it follows from the Hahn-Banach theorem applied to the epigraph of φ that, if x belongs to the interior of the domain of φ, there

is p ∈ R d such that ∀ ∈ R d , φ() ≥ φ(x ) + p| -x.
The set of all those p's is called the subdierential of φ at x, and is denoted by ∂φ(x ). It can be shown that φ is locally Lipschitz on the interior of its domain, and therefore is dierentiable almost everywhere on it. Should that be the case in x, the subdierential is then a singleton: ∂φ(x ) = {∇φ(x )}.

... T (Brenier). Let µ and ν be two Borel probability measures on R d with nite second-order moments-that is, such that

|x | dµ (x ) < ∞ and || dν () < ∞.
Then, if µ is absolutely continuous, there is a unique

T : R d → R d such that ν = T # µ and |x -T (x )| dµ (x ) = min γ ∈Γ( µ ,ν ) |x -| dγ (x , ).
Moreover, there is only one optimal transport plan γ , which is thus necessarily (Id, T ) # µ, and T is the gradient of a convex function φ, which is therefore unique up to an additive constant. There is also a unique (up to an additive constant) Kantorovich potential ψ , which is locally Lipschitz and linked to φ through the relation

φ(x ) = |x | -ψ (x ).
Proof. We know from proposition .. on page that, for a cost c (x ,

) = |x -| , there is a c-concave function ψ such that ψ (x ) dµ (x ) + ψ c () dν () = |x -| dγ (x , ) (...a)
for some optimal transport plan γ ∈ Γ(µ, ν ). We set

φ(x ) := |x | -ψ (x ).
Then, since ψ cc = ψ , this function φ is convex and lower semicontinuous, being a supremum of ane maps:

φ(x ) = |x | -ψ cc (x ) = sup |x | - |x -| + ψ c () = sup |x- || -ψ c () .
This computation also yields the Legendre transform of φ, which is

φ * (x ) = |x | -ψ c (x ).
As φ is convex and lower semicontinuous, it is dierentiable almost everywhere in the interior of its domain-that is, almost everywhere at least in the interior of the convex hull of the support of µ, since µ is absolutely continuous. All we have to do now is to show that the optimal transport map is

T (x ) = ∇φ(x ) = x -∇ ψ (x ).
Notice that equality (...a) translates into φ(x

) dµ (x ) + φ * () dν () = |x dγ (x , ).
As φ(x ) + φ * () ≥ |x, this implies that for γ -a.e. pair (x , ), there is equality. Thus,

∀ z ∈ R d , |z-φ(z) ≤ |x-φ(x ),
which, in turn, means ∈ ∂φ(x ). But φ is dierentiable for a.e. x in the support of µ, and in that case the subdierential is reduced to ∇φ(x ). Therefore, γ = (Id, ∇φ) # µ.

This also shows the uniqueness of γ and T = ∇φ. This φ is unique up to an additive constant as well, and so is ψ .

... Monge-Ampère equation. Regularity results regarding the convex map φ and the optimal map T = ∇φ have been obtained, most notably by Luis A. Caarelli [, , ], using the Monge-Ampère equation: if we denote by f and the respective densities of µ and ν, then, if it is smooth enough, φ must solve

f (x ) = (∇φ(x )) det(∇ φ(x )).
... T (Caarelli). Let U and V be two bounded, open subsets of R d , and let µ and ν be two probability measures respectively on U and V , with densities f and .

If those densities are bounded and bounded away from , and if V is convex, then φ is strictly convex and C ,α on U . Moreover, if f and are C k with k ≥ , then φ is C k+ .

If both U and V are strictly convex with smooth boundaries, the regularity of φ holds even on the boundary of U . In that case, ∇φ and ∇φ * are dieomorphisms, and inverse of each other.

. Extension to the torus for the Riemannian distance between x and , then there is a unique optimal transport plan γ ∈ Γ(µ, ν ) for the cost c (x , ) = d(x , ) , which is induced by the transport map T (x ) = exp x [-∇ψ (x )], with ψ Lipschitz and c-concave . The Kantorovich potential ψ is unique up to an additive constant. for a quadratic cost c :

T d × T d → [, ∞) induced by c : R d × R d → [, ∞) given by c (x , ) := inf k ∈Z d A(x --k ) ,
where A ∈S ++ d is a symmetric, positive-denite matrix, and Az is a shorthand for Az |z. Such a cost arises when one changes the usual metric on T d with the one induced by A in the canonical set of coordinates, and then takes half the resulting squared distance as a cost function.

Before stating and proving the theorem, we however need to adapt Yann Brenier's convex point of view to the torus. We have seen in section . that ψ is a c-concave map if and only if φ(x ) := |x |ψ (x ) is a lower semicontinuous convex map. Something similar is going on here for a quadratic cost, namely:

... Lemma. A map ψ :

T d → R is c-concave for the cost c induced by A ∈S ++ d , if and only if φ(x ) := Ax -ψ (x )
is lower semicontinuous and convex on R d . Then,

ψ c () = A -φ * (),
where φ * is the Legendre transform of φ for the scalar product induced by A.

If ψ is C and such that A -∇ ψ > , then x → x -A -∇ψ (x ) is a dieomorphism T d → T d .
Proof. If ψ is c-concave, then φ is convex and lower semi-continuous, for it can be written as a Legendre transform:

φ(x ) = Ax -ψ cc (x ) = Ax -inf ∈T d c (x , ) -ψ c () = sup ∈R d sup k ∈Z Ax - A(x --k ) + ψ c () = sup ∈R d Ax |- A -ψ c () .
This also shows φ

* () = A -ψ c ().
Conversely, if φ is convex and lower semi-continuous, then it is equal to its double Legendre transform:

φ(x ) = sup ∈R d      Ax |-sup z ∈R d Az |-φ(z)      .
Therefore,

ψ (x ) = Ax -sup ∈R N      Ax |-sup z ∈R d Az |-φ(z)      = inf ∈R d      A(x -) - A + sup z ∈R d Az |-φ(z)      = inf ∈R d A(x -) -inf z ∈R d A(z -) -ψ (z) , i.e. ψ (x ) = ψ cc (x ).
If ψ is C and such that A -∇ ψ > , then A -∇ ψ ≥ ε I d for some ε > . Thus, as φ is convex with a super-linear growth, ∇φ : R d → R d is a dieomorphism, and so is the map ν . The function ψ is a Kantorovich potential; it is smooth, and φ : x → Axψ (x ) is a smooth, strictly convex function on R d . Moreover, the transport map T is optimal for the cost c, and there is no other optimal transport plan but the one it induces.

T : x → x -A -∇ψ (x ). Notice that, if k ∈ Z d , then T (x + k ) = T (x ) + k;
Proof. Let us denote by ∇ A the gradient for the metric induced by A. Then according to Robert J. McCann's theorem ( §.., on page ), there is a Lipschitz function

ψ : T d → R that is c-concave and such that T : x → exp x [-∇ A ψ (x )] pushes µ forward to ν . It is uniquely dened if the condition
ψ dµ = is added, and moreover it is optimal for the Monge-Kantorovich problem. Here on the torus,

exp x [-∇ A ψ (x )] = x -A -∇ψ (x ).
For any x ∈ R d , let φ(x ) := Axψ (x ). Then T (x ) = A -∇φ(x ) sends µ onto ν , seen as periodic measures on R d . Moreover, according to lemma .. on page , φ is a convex function. Now, let V be an open, convex subset of R d , and dene U = (∇φ) -(V ). Then ∇φ sends µ | U onto A # ν | V , and both measures are still absolutely continuous with smooth, bounded, strictly positive densities. Therefore we are entitled to apply Luis A. Caarelli's theorem ( §.., on page ), and thus we get that φ is strictly convex and smooth on U .A sU is arbitrary, φ is strictly convex and smooth on R d . Thus, ψ is also smooth, and T is a dieomorphism.

. The Wasserstein space ... Wasserstein distance W p . If µ and ν are two probability measures on a space X, which will be either the Euclidean space or a Riemannian manifold, then the minimal value for the Monge-Kantorovich problem denes a distance, dubbed the Wasserstein distance, when the cost is c (x , ) = d(x , ) p with d the distance of X:

W p (µ, ν ) := min γ ∈Γ( µ ,ν ) d(x , ) p dγ (x , ) /p .
... Wasserstein space P p (X). For the Wasserstein distance between µ and ν to be nite, it is enough for them to have nite pth-order moments. In other words, W p is a distance on the following subset of the space P (X) of Borel probability measures on X:

P p (X) := µ ∈P(X)         ∀ x ∈ X, d(x , x ) p dµ (x ) < ∞ .
Thanks to the triangular inequality, the condition "for all x " can be replaced by "there is at least one x ".

... P. For any µ, ν ∈P (X),

W (µ, ν ) := inf ψ ∈Lip (X) ψ d(µ -ν ).
Proof. This follows from proposition .. on page , for if ψ is -Lipschitz, then -ψ () ≤ d(x , )ψ (x ) for any x, and thus ψ c = -ψ .

... P. A sequence (µ n ) n ∈N converges for the Wasserstein distance if and only if it narrowly converges and the pth-order moments converge as well. Therefore, if is X compact, then P p (X) = P (X) is also compact.

Proof. See Cédric Villani's rst book [, Theorem .].

As will be shown by the next three propositions, optimal transport lies at the heart of the properties of the Wasserstein distance.

... P. Let µ , µ ∈P p (R d ). Then, any γ ∈ Γ(µ, ν ) optimal for the Monge-Kantorovich problem induces a constant-speed geodesic (µ t ) t ∈[,] , dened by

µ t := [( -t )X + tY] # γ ,
where X(x , ) := x and Y(x , ) := ; that is,

∀ ξ ∈ C b , ξ (z) dµ t (z) = ξ (( -t )x + t) dγ (x , ).
Conversely, any constant-speed geodesic between µ and µ is induced by an optimal transport plan γ ∈ Γ(µ, ν ). Therefore, if µ is absolutely continuous, there is an optimal transport map T between µ and µ , and the geodesic is

µ t := [( -t ) Id +tT ] # µ .
This shows the Wasserstein space is a length space: the Wasserstein distance coincides with the distance induced by the geodesics.

Proof. Let γ be an optimal transport plan between µ and µ . Let also t ∈ [, ], and dene Z t := (t )X + tY. Then, µ t = [Z t ] # γ , and, for any s ∈ [, ], (Z s , Z t ) # γ is a transport plan between µ s and µ t . Therefore,

W p (µ s , µ t ) p ≤ ( -s)x + s - ( -t )x + t p dγ (x , ) ≤| t -s | p W p (µ , µ ) p , that is W p (µ s , µ t ) ≤| t -s |W p (µ , µ ).
Were that inequality to be strict for a pair (s , t ), the triangular inequality would yield W p (µ , µ ) < W p (µ , µ ), which is obviously not possible. Thus,

W p (µ s , µ t ) = |t -s |W p (µ , µ ). Conversely, if (µ t ) t ∈[ ,]
is a constant speed geodesic, then, for any t ∈ [, ], it is possible to "glue" together two optimal transport plans to form π ∈ Γ(µ , µ t , µ ) such that (X, Y) # π and (Y, Z) # π are optimal plans between, respectively, µ and µ t on the one hand, and µ t and µ on the other hand-where

X(x , , z) = x , Y(x , , z) = , Z(x , , z) = z.
We refer to Cédric Villani's rst book on optimal transportation [, Lemma .] for a proof of this gluing lemma . Then,

W p (µ , µ ) ≤ X -Z L p (π ) ≤ X -Y L p (π ) + Y -Z L p (π ) ≤ W p (µ , µ t ) +W p (µ t , µ ) ≤ W p (µ , µ ).
Thus, all the inequalities are, in fact, equalities. This implies (X, Z) # π is optimal and

there is α ∈ [, ] such that Y = ( -α )X + αZ in L p (π ). Therefore, W p (µ , µ t ) = tW p (µ , µ ) yields α = t.
... P. Let µ, ν ∈P(K ), with K a compact subset of R d or a compact manifold. Then, for any μ ∈P(K ), there is a Kantorovich potential ψ between µ and ν for the cost c (x , ) = d(x , ) p /p such that:

lim ε→ + W (( -ε)µ + ε μ, ν ) -W (µ, ν ) ε = ψ d( μ -µ).
A priori, the potential ψ may depend on μ. However, it is obviously no longer the case if the Kantorovich potential is uniquely dened-e.g. if µ or ν is absolutely continuous and strictly positive.

Proof. Let ψ ε be a Kantorovich potential between (ε )µ + ε μ and ν :

ψ ε d[( -ε )µ + ε μ]+ ψ c ε dν = W (( -ε)µ + ε μ, ν ) .
The same lemma allows to prove W p is a distance Then,

W (( -ε)µ + ε μ, ν ) -W (µ, ν ) ε ≤ ψ ε d( μ -µ). Since ψ ε is c-concave, ψ (x ) = inf d (x , ) -ψ c () ,
and consequently, as K is bounded, ψ ε is Lipschitz with a constant that does not depend on ε; so is ψ c ε . By the Arzelà-Ascoli theorem, the family {(ψ ε , ψ c ε )} is therefore relatively compact. Let (ψ , φ) be a limit point such that lim sup

ε→ + ψ ε d( μ -µ) = ψ d( μ -µ).
Then, since ψ (x )

+ φ() ≤ |x -| , we have W (µ, ν ) ≤ lim inf ε→ + W (( -ε)µ + ε μ, ν ) = lim inf ε→ + ψ ε d(( -ε)µ + ε μ) + ψ c ε dν ≤ ψ dµ + φ dν ≤ W (µ, ν ) .
Thus, ψ is a Kantorovich potential between µ and ν, and

lim sup ε→ + W (( -ε )µ + ε μ, ν ) -W (µ, ν ) ε ≤ lim sup ε→ + ψ ε d( μ -µ) ≤ ψ d( μ -µ).
On the other hand,

W (( -ε)µ + ε μ, ν ) ≥ ψ d(( -ε)µ + ε μ) + ψ c dν ≥ W (µ, ν ) + ε ψ d( μ -µ),
and this yields

lim inf ε→ + W (( -ε )µ + ε μ, ν ) -W (µ, ν ) ε ≥ ψ d( μ -µ).
... P. Let µ, ν ∈P (K ), with K a compact subset of R d or K = T d , and assume µ is absolutely continuous. Let ψ is the (unique up to an additive constant)

Kantorovich potential between µ and ν for the cost c (x ,

) = d(x , ) p /p. If ζ is a dieomorphism of K, then lim ε→ W ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε = ∇ψ |ζ dµ.
Proof. As ψ is a Kantorovich potential between µ and ν ,

W ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≥ ψ (x + εζ (x )) -ψ (x ) ε dµ (x ).
Since ψ is Lipschitz (because K is compact), it is dierentiable almost everywhere.

Thus, Lebesgue's dominated convergence theorem yields

lim inf ε→ + W ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≥ ∇ψ (x ) ζ (x ) dµ (x ).
Conversely, Id -∇ψ is an optimal map between µ and ν , so (Id +εζ , Id -∇ψ ) # µ is a transport plan between [Id +εζ ] # µ and ν , and thus

W ([Id +εζ ] # µ, ν ) ≤ [x + εζ (x )] - x -∇ ψ (x ) dµ (x ) ≤ x - x -∇ ψ (x ) +ε ∇ψ (x ) ζ (x ) + ε |ζ (x )| dµ (x ) ≤ W (µ, ν ) + ε ∇ψ (x ) ζ (x ) dµ (x ) + ε |ζ (x )| dµ (x ).
Hence

lim sup ε→ + W ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≤ ∇ψ (x ) ζ (x ) dµ (x ).
. The Benamou-Brenier formula ... According to proposition .. on page , the geodesics in P p (R d ) are all induced by optimal transport plans. Jean-David Benamou and Yann Brenier [] found another characterization, namely that the geodesics should minimize the average kinetic energy of the particles through the transport. That is, the geodesics should minimze

(µ t ) t ∈[ ,] -→ | t (x )| dµ t (x ) dt ,
among all the absolutely continuous curves

(µ t ) t ∈[ ,] with ( t ) t ∈[ ,]
the associated velocity eld given by the continuity equation:

d dt + div (µ) = .
From this, they derived a method to numerically solve the Monge-Kantorovich problem.

.

.. Metric derivative. If (µ t ) t ∈I is an absolutely continuous curve in P p (X ), i.e. if there is ∈ L (I ) such that ∀ s, t ∈ I , W p (µ s , µ t ) ≤ [s ,t]
(ω) dω, then, for almost every t ∈ I , the limit

| μ | t := lim sup h→ W p (µ t , µ t+h ) |h| exists,
e (t ) = sup n ∈N |d n (t )| = sup n ∈N lim h→ |d n (t ) -d n (t + h)| |h| ≤ lim inf t→ W p (µ t , µ t+h ) |h| . But {t n } is dense in I , so W p (µ t , µ t+h ) = sup n ∈N |d n (t + h) -d n (t )|≤sup n ∈N [t ,t+h] |d n (ω)| dω ≤ [t ,t+h]
e (ω) dω. ... Lemma. Let (µ t ) t ∈I be an absolutely continuous curve in P p (R d ). Then, there is a vector eld :

By the

I × R d → R d such that | μ | t = t L p ( µ t ) for almost all t ∈ I . Moreover, in the distributional sense, dµ dt + div(µ) = .
Conversely, if there is a vector eld :

I × R d → R d such that, in the distributional sense, dµ dt + div(µ) = with I t L p ( µ t ) dt < ∞, then (µ t ) t ∈I is absolutely continuous, and | μ | t ≤ t L p ( µ t )
for almost all t ∈ I .

For the proof of this lemma, we refer to the monograph by Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré [, Theorem ..].

... T (Benamou-Brenier). Let p ∈ (, ∞) and µ , µ ∈P p (X) with

X = R d or X = T d . Then W p (µ , µ ) p = inf ,ρ [ ,] X | t (x )| p dµ t (x ) dt ,
where the inmum runs among all pairs (µ, ) such that (µ t ) t ∈[,] is a continuous curve between µ and µ , and :

[, ] × X → R d is a vector eld such that t ∈ L p (µ t ) for almost all t ∈ [, ],
and, in the distributional sense,

dµ dt + div(µ) = .
Proof . Let (µ t ) be a curve of absolutely continuous, smooth probability measures on T d , and let be a vector eld smooth in space that, together with (µ t ), solve the continuity equation. Assume

t C dt < ∞. Then, the solution t → X s ,t (x ) of the equation dX s ,t /dt = t (X s ,t ), with X s ,s (x ) = x,
is dened for all t ∈ [, ] (if we were not working on a compact space without boundary, there would be a diculty here

). For ξ ∈ C ∞ ([, ] × T d ), we set φ t (x ) := - t ξ s (X t ,s (x )) ds. Since X t ,s (X ,t (x )) = X ,s (x ), dφ t dt (X ,t ) + t (X ,t ) ∇φ t (X ,t ) = d dt φ t (X ,t ) = ξ t (X ,t ), and as x → X ,t (x ) is a dieomorphism, this implies dφ/dt + ∇φ = ξ . Thus, dφ t dt (x ) + t (x ) φ t (x ) dµ t (x ) dt = ξ t (x ) dµ t (x ) dt .
On the other hand, since (µ, ) solves the continuity equation and φ = ,

dφ t dt (x ) + t (x ) ∇φ t (x ) dµ t (x ) dt = - φ (x ) dµ (x ).
This implies µ t = [X ,t ] # µ . Indeed, let μt := [X ,t ] # µ , and σ := μµ. Then, according to the previous computations, which also hold for μ, for any

ξ ∈ C ∞ ([, ] × T d ), ξ t (x ) dσ t (x ) dt = - φ (x ) dσ (x ) = . Therefore, since [X , ] # µ = µ , W p (µ , µ ) p ≤ |X , (x ) -x | p dµ (x ) ≤ |X ,t (x )| p dt dµ (x )
and thus, as X s ,t = t (X s ,t ) and

µ t = X ,t # µ , W p (µ , µ ) p ≤ | t (X ,t (x ))| p dµ (x ) dt ≤ | t (x )| p dµ t (x ) dt .
. We no longer assume anything about µ and µ , but that they are probability measures on T d . If (µ t ) is a continuous curve between them, and if is a vector eld solving the continuity equation, with t ∈ L p (µ t ), then, taking a positive mollier φ ε , we set

µ ε t = φ ε * µ t .A sφ ε * ( t µ t )
is absolutely continuous, it has a density ε t with respect to µ ε t , which is positive. Thus, (µ ε , ε ) also solves the continuity equation, and

(µ ε t ) is still a continuous curve. Moreover, setting m ε = min φ ε , ε t C ≤ φ ε * ( t µ t ) C (m ε + µ ε t C m ε . But, µ ε t C < C ε , and, as φ ε * ( t µ t )(x ) = φ ε (x -) t () dµ t () ≤ φ ε (x -•) L q ( µ t ) t L p ( µ t ) ≤ φ ε C t L p ( µ t ) ,
we must also have

φ ε * ( t µ t ) C ≤ C ε t L p ( µ t )
. We can therefore assume

ε t C dt ≤ C ε t L p ( µ t ) dt ≤ C ε | t (x )| p dµ t (x ) dt /p < ∞.
Then, according to the previous computations,

W p (µ ε , µ ε ) p ≤ | ε t (x )| p dµ ε t (x ) dt .
According to Jensen's inequality, since (a, b) → |a| p /b p -is convex and homogeneous of degree on R × (, ∞), and φ ε (x -•)µ t is a bounded measure,

| ε t (x )| p µ ε t (x ) = t ()φ ε (x -) dµ t () p φ ε (x -) dµ t () p -≤ | t ()| p φ ε (x -) dµ t ().
Thus,

W p (µ ε , µ ε ) p ≤ | ε t (x )| p dµ ε t (x ) dt ≤ | t ()| p dµ t () dt .
Then, letting ε → , we nally get

W p (µ , µ ) p ≤ | t ()| p dµ t () dt .
. Conversely, if µ and µ are absolutely continuous, with strictly positive, smooth densities, then according to Yann Brenier's theorem ( §.., on page ) and Luis A. Caarelli's theorem ( §.., on page ), there is a dieomorphism T :

T d → T d such that µ = T # µ . Then, if we set t = (T -Id) • [( -t ) Id +tT ] -and let µ t be the density of [( -t ) Id +tT ] # µ, we get dµ dt + div(µ) = and W p (µ , µ ) p = | t (x )| p dµ t (x ) dt .
. In the general case, let γ ∈ Γ o (µ , µ ) be an optimal plan, and let (µ t ) t ∈[,] be the geodesic induced by γ . Dene then a probability measure π on

[, ] × T d with ξ (t , z) dπ (t , z) = ξ (t , z) dµ t (z) dt = ξ (t , ( -t )x + t) dγ (x , ) dt . Then, if ξ ∈ C ∞ c ((, ) × T d ), {ξ t+h (z) -ξ t (z)} dπ (t , z) = ξ t (z) dµ t -h (z) - ξ t (x ) dµ t (z) dt ≤ ξ t (( -t + h)x + (t -h)) -ξ t (( -t )x + t) dγ (x , ) dt ≤ h ∇ξ t (( -t + sh)x + (t -sh)) x - ds dγ (x , ) dt ≤ hW p (µ , µ ) ∇ξ t (( -t + sh)x + (t -sh)) q ds dγ (x , )dt /q
and thus, dividing by h and letting h → ,

d dt ξ t (z) dπ (t , z) ≤ W p (µ , µ )∇ξ L q (π ) . For ξ ∈ C ∞ ((, ) × T d ), we set L(∇ξ ) := - d dt ξ t (z) dπ (t , z),
then this L can be extended into a continuous linear form on L q (π ). Thus, there is

∈ L p (π ) such that L p (π ) ≤ W p (µ , µ ) and ∀ ξ ∈ C ∞ ((, ) × T d ), d dt ξ t (z) + t (z) ∇ξ t (z) dπ (t , z) = .
This implies that

dµ dt + div(µ) = and | t (z)| p dµ t (z) dt ≤ W p (µ , µ ) p .

Chapter

The inverse function theorem of Nash and Moser

... The Nash-Moser theorem is an extension of the well-known inverse function theorem to maps between Fréchet spaces. The rst steps toward such a theorem were made in by John Nash [], in his proof that one could embed any Riemannian manifold into some Euclidean space. A decade later, Jürgen Moser [, ] exposed a general method, which has ever since known many applications and developments.

We will here follow the presentation made by Richard S. Hamilton [], though keeping only the elements required to come to a minimal working statement, which is enough to satisfy our needs.

... Compared with the standard inverse function theorem, two conditions need to be added for a map ζ between two Fréchet spaces to be invertible near : rst, that Dζ itself be invertible on a whole neighborhood, since this does not follow any longer from the invertibility of Dζ (); second, there should be "reasonable" bounds on ζ , Dζ , and [Dζ ] -, i.e. ζ (u) n for instance should be bounded at most by +u n+r for some constant r ≥ independent of n. In mathematical terms, we will say that ζ , Dζ and [Dζ ] -need to satisfy some "tame" estimates.

If ζ () = , and is xed and close to , a way to get u such that = ζ (u) is to use a continuous version of Newton's method and nd a solution of the equation

u (t ) = λ[Dζ (u (t ))] -( -ζ (u (t ))),
starting for instance from u () = , since then ζ (u (t )) = (e -λt ) → . As such an might not have a solution if ζ is a map between Fréchet spaces, we will use a smooth family of operators (S t ) t ≥ such that S t → Id when t →∞and each S t takes its values in a nite-dimensional subspace, and then solve

u (t ) = λ[Dζ (S t u (t ))] -S t ( -ζ (u (t ))).
The existence of an appropriate family of nite-dimensional subspaces will be guaranteed by working on a particular class of Fréchet spaces, the so-called "tame" Fréchet spaces. Fortunately, the Fréchet space we are interested in, namely C ∞ (T d ), is tameas will be shown in the last section.

. Definitions and statements ... We will now state the theorem and its implicit-function corollary, but, beforehand, we need to introduce a few denitions.

... Graded Fréchet space. This is the name given to a Fréchet space F endowed with a family of increasingly stronger seminorms (• n ∈N ), so that

∀u ∈ F, u ≤ u ≤•••≤ u n ≤•••.
For any q ∈ N and ρ > , we set

B q (ρ) := h ∈ F      h q < ρ and B q (ρ) := h ∈ F      h q ≤ ρ .
Ivar Ekeland recently showed this is not the only way, by proving a more general inverse function theorem using his variational principle instead of Newton's method [].

... Tame linear map, tame isomorphism. A tame linear map L :F→ G is a linear map between two graded Fréchet spaces such that, for some r , b ∈ N, the following tame estimate is satised:

∀ n ≥ b, ∃ C n > , ∀ ∈ F, Lu G n ≤ C n u F n+r .
Such a map L is a tame isomorphism if it is invertible, and both L and L -are tame linear maps.

... Set of exponentially decreasing sequences Σ(E). For a Banach space (E, • E ), the set of exponentially decreasing sequences in E is dened by:

Σ(E) := u ∈ E N      ∀ n ∈ N, u n < ∞ where u n := ∞ k= e nk u k E
Endowed with the seminorms (• n ) n ∈N , it is a graded Fréchet space. Notice that the seminorms could also be dened for n ≤ .

... Tame Fréchet space. A graded Fréchet space F is called a tame Fréchet space if there is a Banach space E and two tame linear maps L :F→ Σ(E) and K :

Σ(E) → F such that K • L is the identity of F.
... Tame map, tame estimate. Let F and G be two graded Fréchet spaces, and Ω ⊂ F be an open subset. A map ζ : Ω → G is said to be tame if it is continuous and, for every point u ∈ Ω, there is a neigkorhood U of u and some r , b ∈ N such that

∀ n ≥ b, ∃ C n > , ∀u ∈ U , ζ (u) G n ≤ C n +u F n+r .
... Smooth tame map. Let F and G be two graded Fréchet spaces, and Ω ⊂ F be an open subset. A map ζ : Ω → G is said to be a smooth tame map if it is smooth and all its Gâteau derivatives are tame.

... T (Nash-Moser). Let F and G be two tame Fréchet spaces, and Ω ⊂ F an open subset. Let ζ : Ω → G be a smooth tame map such that, for any u ∈ Ω,

Dζ (u) :F→ G is invertible. If [Dζ ] -: Ω × G → F is a smooth tame map, then ζ is
locally invertible, and, locally, its inverse is always a smooth tame map.

... C (implicit functions theorem). Let F, G and H be tame spaces, U an open subset of F, V an open subset of G. Assume that ξ : U × V → H is a smooth tame map, and that there are

u ∈ U , ∈ V such that ξ (u , ) = . If, for all u ∈ U , ∈ V , w ∈ H, there is a unique h ∈ G such that D ζ (u, )h = w,
ν : U → V such that ∀u ∈ U , ∀ ∈ V , ξ (u, ) = ⇔ = ν (u).
Proof of the corollary. We dene a smooth tame map ζ :

U × V → F × H by setting ζ (u, ) = (u, ξ (u, )).
Then, for all (u, )

∈ U × V , Dζ (u, ) =        Id D u ζ (u, ) D ζ (u, )       
is invertible, and (u, , q, w ) → [Dζ (u, )] -(q, w ) is a smooth tame map. Therefore, according to the Nash-Moser theorem, in a neighborhood U × V of (u , ), ζ is invertible, and

ζ -: ζ (U ×V ) → U ×V is a smooth tame map. Let U ×W ⊂ ζ (U ×V )
be a neighborhood of (u , ), and U ×V ⊂ ζ -(U ×W ) be a neighborhood of (u , ).

We then take ν :

U → V such that (u, ν (u)) = ζ -(u, ).
. Organization of the proof ... In the next paragraphs, let us simplify the proof we need to give by a sequence of reductions to easier situations. The injectivity of ζ will then be proved in section .

(proposition .. on page ). In section ., we will introduce the smoothing operators that will allow us to prove the surjectivity in section . (proposition .. on page ).

At last, we will deal with the smooth-tameness of ζ -in section . (proposition .. on page ).

... Lemma. It is possible to assume ∈ Ω, with ζ () = , and F = G = Σ(E), for some Banach space E.

Proof. Since Dζ () :F→ G is linear tame and invertible, with an inverse map [Dζ ()] -:G→ F which is also linear tame, F and G are isomorphic and can be identied. Since F is a tame Fréchet space, we can assume F = G = Σ(E) for some

Banach space E.

... Lemma. One can assume that there is r ∈ N such that, for all n ≥ , there is

C n > such that, if u r ≤ , for all h, k ∈ Σ(E), ζ (u) n ≤ C n u n+r , (...a) Dζ (u)h n ≤ C n h n+r + h u n+r , (...b) D ζ (u)h h n ≤ C n h h n+r + h n+r h + h h u n+r , (...c) [Dζ (u)] -k n ≤ C n k n + k u n+r . (...d) Proof. Since ζ , Dζ , D ζ and [Dζ ]
-are all tame, there is a neighborhood U of , and

r , b ∈ N such that, if u, h, h , h , k ∈ U , for any n ≥ b, ζ (u) n ≤ C n (+u n+r ) , Dζ (u)h n ≤ C n (+h n+r + u n+r ) , D ζ (u)h h n ≤ C n (+h n+r + h n+r + u n+r ) , [Dζ (u)] -k n ≤ C n (+k n+r + u n+r ) .
This neighborhood U necessarily contains a small ball B a (ρ), and we can assume a ≥ r . Then, since for any h ∈ Σ(E), the vector ρh/h a is in U , we obtain that for

any u ∈ Σ(E) such that u a ≤ ρ and any h, h , h , k ∈ Σ(E), ζ (u) n ≤ C n (+u n+r ) , Dζ (u)h n ≤ C n (h n+r + h a u n+r ) , D ζ (u)h h n ≤ C n (h n+r h a + h a h n+r + h a h a u n+r ) , [Dζ (u)] -k n ≤ C n (k n+r + k a u n+r ) .
For any q ∈ Z, we dene τ :

Σ(E) → Σ(E) by τ q (u) k = e qk u k . Then, τ q (u) n = ∞ k= e k (n+q) u k = u n+q
Thus, τ q is a tame linear map. So, for any p, q ∈ Z, the map τ p • ζ • τ q is still smooth tame, and

D(τ p • ζ • τ q )(u)h = τ p [Dζ (τ q (u))]τ q (h) , D (τ p • ζ • τ q )(u)h h = τ p [D ζ (τ q (u))]τ q (h )τ q (h ) , [D(τ p • ζ • τ q )(u)] -k = τ -q [Dζ (τ q (u))] -τ -p (k ) .
Therefore, if we replace ζ with τ p • ζ • τ q for some p, q, and compose with a dilatation so as to have an estimate on a ball of radius , then, if n + p ≥ b and nq ≥ b and

u a+q ≤ , ζ (u) n ≤ C n +u n+p+r +q , Dζ (u)h n ≤ C n h n+p+r +q + h a+q u n+p+r +q , D ζ (u)h h n ≤ C n h n+p+r +q h a+q + h a+q h n+p+r +q + h a+q h a+q u n+p+r +q , [Dζ (u)] -k n ≤ C n k n -q+r -p + k a -p u n -q+r +q .
Increasing a, b, and r if necessary, we will assume a = b = r . Then, for p = r , q = -r , we get that, if n ≥ bp = -r and n ≥ q + b = , and if u ≤ ,

ζ (u) n ≤ C n (+u n+r ) , Dζ (u)h n ≤ C n (h n+r + h u n+r ) , D ζ (u)h h n ≤ C n (h n+r h + h h n+r + h h u n+r ) , [Dζ (u)] -k n ≤ C n (k n + k -r u n+r ) .
We then set r = r .A sζ () = ,

ζ (u) = Dζ (tu)u dt ,
and thus, if u ≤ ,

ζ (u) n ≤ C n u n+r + u u n+r ≤ C n u n+r .
. Injectivity

... P. If ζ satises the assumption of theorem .. on page and of the previous section, then there exist ε > and some C > such that

∀u, ∈ B r (ε), u -≤ C ζ (u) -ζ () .
Proof. Let u, ∈ B r (ε ) for some ε ∈ (, ) that will be xed later on. Then, according to Taylor's formula,

ζ () = ζ (u) +Dζ (u)( -u) + D ζ (( -t )u + t)( -u) ( -t ) dt .
This implies

-u = [Dζ (u)] - ζ () -ζ (u) - D ζ (( -t )u + t)( -u) ( -t ) dt . Using (...d), since ( -t )u + t r ≤ ε we get -u ≤ C (+ε ) ζ (u) -ζ () + D ζ (( -t )u + t)( -u) dt . (...a)
According to (...c),

D ζ (( -t )u + t)( -u) ≤ C r -u -u r + -u ( -t )u + t r , which, since u, ∈ B r (ε ), implies D ζ (( -t )u + t)( -u) ≤ Cε -u . (...b)
Thus, (...a) becomes

-u ≤ C (ζ (u) -ζ () + ε -u ) ,
and the result follows as soon as Cε < /. Then, (...b) becomes

D ζ (( -t )u + t)( -u) ≤ -u .
Let us put the last inequality into ... Lemma. If ε is given by proposition .. on the preceding page, then

∀u, ∈ B r (ε), D ζ (( -t )u + t)( -u) ≤ -u .
. Smoothing operators ... In this section, we introduce the operators (S t ) t ≥ that will enable us to prove ζ is surjective in the next section. In particular, we will study the solutions of the

Chapter . The Nash-Moser inverse function theorem equation

x (t ) + λS t x (t ) = (t ),
and give estimates on x (t ) n .

... Smoothing operator. Let σ : R → [, +∞) be a smooth function such that σ (t ) = when t ≤ and σ (t ) = when t ≥ , with σ strictly increasing on (, ).

The smoothing operator S t : Σ(E) → Σ(E) is dened by:

(S t u) k := σ (t -k )u k for all k ∈ N and u ∈ Σ(E).
... Lemma. Let n, q ∈ N. Then, for any u ∈ Σ(E),

∀ t ∈ R, S t u n+q ≤ e qt u n and u -S t u n ≤ C q e -qt u n+q .
Proof. Since σ ≤ always, and σ (tk ) = as soon as t ≤ k,

S t u n+q ≤ k ≤t e (n+q)k u k ≤e qt k ≤t e nk u k ≤e qt u n .
On the other hand, since

σ (t -k ) = as soon as t -≥ k, u -S t u n ≤ t -≤k
e nk u k ≤e -q(t -)

t -≤k e (n+q)k u k ≤e q e -qt u n+q .

... Lemma. Let T > . Then for t ≤ T , the smoothing operator S t takes its values into a nite-dimensional subspace Σ T (E) := Span{e i | i ≤ T }, where we have set

e i := (δ k ,i ) k ∈N .
... Lemma (Landau-Kolmogorov inequalities). Let p, q ∈ N. Then, for any

θ ∈ (, ), if ( -θ )p + θq ∈ N, ∀u ∈ Σ(E), u (-θ )p+θq ≤ C n ,p ,q u -θ p u θ q .
The name is usually used for such equalities in

C ∞ with f n := f C n or f n := f H n .
Proof. Let n = (θ )p + θq, and assume p ≤ q. According to lemma .. on the previous page,

u n ≤ S t u n + u -S t u n ≤ C e t (n -p) u p + e -t (q -n) u q .
Then, if t is such that e t (n -p) u p = e -t (q -n) u q , i.e. e t (q -p) = u q /u p , since np = θ (qp) and qn = (θ )(qp), we get the desired result.

.

.. Lemma. Let λ > , x ∈ C ([, T ]; Σ(E)), and ∈ C ([, T ]; Σ(E)) be such that ∀ t ∈ [, T ], x (t ) + λS t x (t ) = (t ),
where S t is the operator introduced in denition .. on the preceding page. Then, for any n, q ∈ N and assuming q ∈ (, λ),

T e qt x (t ) n dt ≤ C q ,λ x () n+q + T (t ) n+q + e qt (t ) n dt ,
where the constant C q ,λ does not depend on T .

Proof. We set a k (s , t First of all, notice that a k (s, t ) ≤ . But as σ (ωk ) = when ω ≥ k +,

) := exp -λ t s σ (ω -k ) dω for s < t. Then, since a k (t , t ) = and d ds a(s , t ) = λS s a(s, t ), the equation x (t ) + λS t x (t ) = (t ) yields x k (t ) = a k (t , t )x k (t ) = a k (, t )x k () + t d ds [a k (s, t )x k (s)] ds = a k (, t )x k () + t λS s a k (s , t )x k (s) + a k (s, t )x k (s) ds = a k (, t )x k () + t a k (s, t ) k (s)
• if s ≤ k +≤ t, then t s σ (ω -k ) dω ≥ (t -k -) and a k (s , t ) ≤ e -λ(t -k -) • if k +≤ s, then a k (s, t ) ≤ e -λ(t -s) .
Thus, assuming T > k +, and

λ > q > , T e qt a k (, t ) dt ≤ k+ e qt dt + T k+ e qt e -λ(t -k -) dt ≤ C q ,λ e q(k+) + e λ(k+) e -(λ -q)(k+) ≤ C q ,λ e qk .
Therefore,

T e qt a(, t )x () n dt = T e qt ∞ k= e kn a k (, t )x k ()≤C q ,λ x () n+q .
All we have to do now is to bound the second part in (...a). By Fubini's theorem, e tq e -λ(t -s) dt ≤ C q ,λ e qs

We can sum up the situation with the following bound,

T s e tq a k (s, t ) dt ≤ C q ,λ e qk + e qs .

Thus,

T s

e qt a(s , t )(s) n dt = T s e qt ∞ k= e kn a k (s, t ) k (s) dt = ∞ k= e kn k (s) T s e qt a k (s , t ) dt ≤ C q ,λ (s) n+q + e qs (s) n ,
and this, injected into (...b), completes the proof.

. Surjectivity ... To show that, for every close to , there is ū, also close to , such that ζ ( ū) = , we will solve the following :

u (t ) = λ[Dζ (S t u (t ))] -S t ( -ζ (u (t ))),
and show that the solution u (t ) is dened on [, +∞) and converges to some ū when t tends to innity, with ζ ( ū) = . The convergence will be proved thanks to a series of

estimates involving u (t ), x (t ) = -ζ (u (t )), and (t ) = [Dζ (S t u (t )) -Dζ (u (t ))]u (t ).
It will be shown that

x (t ) + λS t x (t ) = (t )
and this second will provide useful estimates, thanks to lemma .. on page .

... Lemma. Let us x λ ∈ R. Then, possibly decreasing ε (initially given by proposition .. on page ) and increasing r (from lemma .. on page ), for any

∈ B r (ε), for some δ > there is a unique u ∈ C ([, δ ); B r (ε )) such that u () = and u (t ) = λ [Dζ (S t u (t ))] - S t ( -ζ (u (t ))) for t ∈ [, δ ).
Proof. We divide the proof in four steps.

.

If Φ t (u) := (S t (u), S t ( -ζ (u)) and Ψ()h := λ[Dζ ()] -h, then u (t ) is a solution if and only if u (t ) = Ψ • Φ t (u (t )
) and u () = .

. According to lemma .. on page , for any t ≤ T the smoothing operator

S t : Σ(E) → Σ(E)
takes its values into a nite-dimensional subspace Σ T (E) where all the seminorms are equivalent norms. Since

D u Φ : [, T ] × Ω × Σ(E) → Σ T (E) × Σ T (E)
is a smooth tame map, increasing r and decreasing ε if necessary, for any t ∈ [, T ],

∀u ∈ B r (ε ), ∀ h ∈ B r (ρ), D u Φ t (u)h ≤ C +h r + u r .
Then, as for any h ∈ Σ(E), we always have ρh/h r ∈ B r (ρ), we can, more generally, say that

∀u ∈ B r (ε), ∀ h ∈ Σ(E), D u Φ t (u)h ≤ C h r ,
and therefore,

∀u, ∈ B r (ε ), Φ t (u) -Φ t () ≤ C u -r . Notice that, if Φ t (u) = ( , h), then = S t (u) ≤ u ≤ ε, and h ≤ -ζ (u) ≤ + C u r ≤ C ε.
Thus, maybe decreasing ε again, as Ψ :

(Σ T (E) ∩ B (ε )) × (Σ T (E) ∩ B (C ε) → Σ(E)
is also smooth tame and all the seminorms are equivalent on Σ T (E), we could in the same way show

∀ , w , ∈ Σ T (E) ∩ B (ε), ∀ h, k ∈ Σ T (E) ∩ B (C ε ), Ψ()h -Ψ(w )k r ≤ C ( -w + h -k ) . . If for some δ > we set X = (Σ T (E) ∩ B (ε )) × (Σ T (E) ∩ B (C ε) and Ξ( , h)(t ) := Φ t t Ψ( (s))h(s) ds for , h ∈ C ([, δ ]; X),
then Ξ is well-dened and is a contraction, at least for δ small enough, since

Ξ( , h) -Ξ(w , k ) ∞ ≤ Cδ ( -w ∞ + h -k ∞ ). Moreover, if δ is small enough, then C ([, δ ]; X) is stable, as (s) r ≤ C T (s)
and thus

t Ψ( (s))h(s) ds ≤ C δ h(s) + h(s) (s) r ds ≤ Cδε,
and we can take δ such that Cδ ≤ .

. By the xed-point theorem, there is a unique

( , h) ∈ C ([, δ ]; X) such that Ξ( , h) = ( , h). Then the curve u (t ) := t Ψ( (s))h(s) ds is such that ( (t ), h(t )) = Φ t (u (t )), so u (t ) = t Ψ • Φ s (u (s)) ds.
This proves the existence of a solution, at least on some interval [, δ ]. Moreover, δ has also been chosen so as to ensure u (t ) ∈ B r (ε).

... Lemma. Let u ∈ C ([, T ), B r (ε)) be the curve given by lemma .. on page , dened on some interval [, T ). Then, if

x (t ) = -ζ (u (t )), ∀ n ≥ , ∀ q ∈ N, ∃ C n ,q > , ∀ t ∈ [, T ), u (t ) n+q ≤ C n ,q ,λ e qt x (t ) n + u (t ) n+r x (t ) . Since u (t ) r ≤ ε, this implies u (t ) q ≤ C q e qt x (t ) .
There is no particular condition on q, and C n ,q ,λ does not depend on T .

Proof. Let x (t ) = -ζ (u (t ). Then u (t ) = λ [Dζ (S t u (t ))] -S t x (t ).
According to (...d), since ε < , for any n ≥ , we have

u (t ) q = λ[Dζ (S t u (t ))] -S t x (t ) n+q ≤ λC n+q S t x (t ) n+q + S t x (t ) S t u (t ) n+q+r .
Now, the result follows from lemma .. on page .

... Lemma. Let u ∈ C ([, T ), B r (ε )) be the curve given by lemma .. on page , dened on some interval [, T ). Then, if

x (t ) := -ζ (u (t )) and (t ) := [Dζ (S t u (t )) -Dζ (u (t ))] u (t ),
we have

∀ q ≥ , ∃ C q > , ∀ t ∈ [, T ), (t ) q ≤ C q u (t ) q+r x (t ) .
Once again, there is no condition on q, and the constant C q does not depend on T .

Proof. Notice that:

[Dζ () -Dζ (u)] = D ζ (( -ω)u + ω) ( -u) dω, therefore (t ) = D ζ (( -ω)u (t ) + ωS t u (t ))(S t u (t ) -u (t ))u (t ) dω.
Using (...c), we get that, for q ≥ , (t

) q ≤ C q S t u (t ) -u (t ) u (t ) q+r + S t u (t ) -u (t ) q+r u (t ) + S t u (t ) -u (t ) u (t ) u (t ) q+r .
According to lemma .. on page , S t u (t )u (t ) ≤ e -mt u (t ) m , and therefore

(t ) q ≤ C e -(q+r )t u (t ) q+r u (t ) q+r + u (t ) q+r u (t ) + u (t ) u (t ) u (t ) q+r .
Now, lemma .. on page yields u (t ) m ≤ C m e mt x (t ) , and thus, as u (t ) r < ε, we get:

(t ) q ≤ C u (t ) q+r x (t ) + ε x (t ) u (t ) q+r . ... Lemma. Let u ∈ C ([, T ), B r (ε )
) be the curve given by lemma .. on page .

Then, if λ > r and if r is small enough,

∃ C > , T e r t x (t ) dt ≤ C r
The constant does not depend on T .

Proof. According to lemma .. on page , as long as λ > r > ,

T e r t x (t ) dt ≤ C r ,λ x () r + T (t ) r + e r t (t ) dt
Notice that x () = . Thanks to lemma .. on the preceding page, we get

T e r t x (t ) dt ≤ C r ,λ r + T u (t ) r x (t ) + e r t u (t ) r x (t ) dt .
Since according to lemma .. on page , u (t ) q ≤ Ce qt x (t ) , we have

u (t ) r ≤ Ce r t t e r s x (s) ds, u (t ) r ≤ C t e r s x (s) ds.
Chapter . The Nash-Moser inverse function theorem

Thus, T e r t x (t ) dt ≤ C        r + T e r t x (t ) dt        .
If we set κ := T e r t x (t ) dt, then κ ≤ C ( r + κ ). Therefore, κ -Cκ ≤ C r . But we always have κ -Cκ ≤ /C with equality only for κ = /C, so if C r ≤ /C, we can ensure κ ∈ [, /C], as κ depends continuously on T and

κ = for T = . But then κ ≤ C r -Cκ ≤ C r . ... Lemma. Let u ∈ C ([, T ), B r (ε)
) be the curve given by lemma .. on page .

We assume λ > r +. Then, if r is small enough,

∀ n ≥ r , ∀ q ∈ N, ∃ C n ,q > , ∀ t ∈ [, T ), t u (s) n+q ds ≤ C n ,q e qt n .
There is no condition on q, and C n ,q does not depend on T .

Proof. We proceed by induction on n, starting from n = r . According to lemma .. on page , u (t ) r +q ≤ Ce (r +q)t x (t ) ; therefore, assuming r small enough and using lemma .. on the preceding page, The case n = r is thus proved.

Let us now proceed with the induction, and assume that, for some n ≥ r ,we have t u (s) n+q ds ≤ Ce qt n for any q ≥ . From lemma .. on page , as nr ≥ , we get

t u (s) n++q ds ≤ C t e (r +q+)s x (s) n -r + n x (s) ds. (...b) Since λ > r +, lemma .. on page yields t e (r +)s x (s) n -r ds ≤ C n+ + t (s) n+ + e (r +)s (s) n -r ds .
But, using lemma .. on page , as u (s) n+m ≤ Ce ms n , we get

(s) n+ ≤ C u (s) n++r x (s) ≤ Ce (r +)s n x (s) , (s) n -r ≤ C u (s) n x (s) ≤ C n x (s) .
Thus, From lemma .. on page , as u (s) r +m ≤ Ce ms r , it follows

t e (r +)s x (s) n -r ds ≤ C n+ + n t e (r
(s) r + ≤ C u (s) r + x (s) ≤ C e (r +)s r x (s) , (s) r ≤ C u (s) r x (s) ≤ C r x (s) .
This yields t e (r +)s x (s) ds ≤ C r + + r t e (r +)s x (s) ds .

Thus, if r is small enough,

t e (r +)s x (s) ds ≤ C r + ,
Chapter . The Nash-Moser inverse function theorem and with this estimate, (...c) becomes t u (s) n++q ds ≤ Ce qt n+ + n r + .

However, setting θ = /(n +r ), as

r + = ( -θ )r + θ (n +) and n = θr + ( -θ )(n +),
we infer from lemma .. on page that

r + n ≤ r n+ ≤ C n+ .
... P. For with r small enough, there is a unique ū ∈ Σ(E) such that ζ ( ū) = , and

∀ n ≥ r , ū n ≤ C n n .
Proof. Let ∈ B r (δ ) with δ small enough and λ > r

+. If u ∈ C ([, T ), B r (ε)) is
given by lemma .. on page , and is dened on a maximal interval [, T ), then according to lemma .. on page (u (t )) t ∈[,T ) is Cauchy when t → T , and thus converges to some u T . From lemma .. on page , it follows that

∀ n ≥ r , ū n ≤ C n n .
Thus, by taking r small enough, we can ensure u T ∈ B r (ε/). But this implies T = ∞, since if it were not the case, by starting over from u T , we could extend u in B r (ε) beyond T , contradicting its maximality.

As

u (t ) = λ[Dζ (S t u (t ))] - S t ( -ζ (u (t )))
, we get u (t ) also converges when t tends to innity. On the other hand, since the constants from lemma .. on page do not depend on T , ∞ u (s) n ds < ∞, and therefore u (t ) → when t →∞. This, in turn, implies

ζ (u (t )) → = ζ (u ∞ ).
Uniqueness follows from proposition .. on page .

. Smoothness and tame estimates ... Lemma. Let ε > be the radius given by proposition .. on page . Then, for all u, ∈ B r (ε ) and n ∈ N,

u -n ≤ C n ζ (u) -ζ () n + u n+r + n+r ζ (u) -ζ () .
Proof. As in the proof of proposition .. on page , we start from Taylor's formula, which yields

-u = [Dζ (u)] - ζ () -ζ (u) - D ζ (( -t )u + t)( -u) ( -t ) dt .
and, using (...d), we get

-u n ≤ C n ζ (u) -ζ () n + D ζ (( -t )u + t)( -u) n dt +u n+r ζ (u) -ζ () + D ζ (( -t )u + t)( -u) dt . (...a)
On the one hand, from (...c) it follows

D ζ (( -t )u + t)( -u) n ≤ C n u -u -n+r + u - ( -t )u + t n+r ≤ C u n+r + n+r u -.
Thanks to the bounds from proposition .. on page , this yields

D ζ (( -t )u + t)( -u) n ≤ C n u n+r + n+r ζ (u) -ζ () , (...b)
On the other hand, from lemma .. on page we get

D ζ (( -t )u + t)( -u) ≤ -u ≤ C ζ () -ζ (u) .
Putting the last two inequalities into (...a), we get the result.

Chapter . The Nash-Moser inverse function theorem ... Lemma. Let ε > be the radius given by proposition .. on page . Then, for u, ∈ B r (ε ), we have

∀ n ≥ , -u -[Dζ (u)] -(ζ () -ζ (u)) n ≤ C n u -n+r u -+ u n+r u - r .
Proof. Once again, we start from Taylor's formula

ζ () = ζ (u) +Dζ (u)( -u) + D ζ (( -t )u + t)( -u) ( -t ) dt , which yields -u -[Dζ (u)] -(ζ () -ζ (u)) = -[Dζ (u)] - D ζ (( -t )u + t)( -u) ( -t ) dt ,
Then, using (...d), we get

-u -[Dζ (u)] -(ζ () -ζ (u)) n ≤ C n D ζ (( -t )u + t)( -u) n ( -t ) dt +u n+r D ζ (( -t )u + t)( -u) ( -t ) dt .
Thanks to (...c),

D ζ (( -t )u + t)( -u) n ≤ C n -u n+r -u + ( -t )u + t n+r -u ≤ C n (+t u -) -u n+r -u + u n+r -u ,
and thus, since ur ≤ ε,

D ζ (( -t )u + t)( -u) n ≤ C -u n+r -u + u n+r -u . Now, (...c) yields D ζ (( -t )u + t)( -u) ≤ C n -u -u r + ( -t )u + t r -u ≤ C n (+ε) -u r .
... P. For any let ū = ζ -( ) be the unique antecedent given by proposition .. on page . Then ζ -is smooth, and all its derivatives satisfy a tame estimate.

Proof. From proposition .. on page , we already know there is an estimate

∀ n ≥ r , ζ -(u) n ≤ C n u n .
Then, lemma .. on page also shows that ζ -is continuous. Furthermore, lemma .. on page yields

ζ -(u + h) -ζ -(u) -[Dζ (ζ -(u))] -h n ≤ C n h n+r h + u n+r h r ,
which proves that ζ -is Gâteaux-dierentiable, and

Dζ -(u)h = Dζ (ζ -(u)) - h.
Thus ζ -is smooth, and the tames estimates for its derivatives follow from the tames estimates of [Dζ ] -and ζ -.

. Tameness of some usual spaces ... This chapter would not be complete if we did not show that C ∞ (T d ) is tame. This is done in three steps: rst, we introduce a space F and prove it is tame; then, thanks to the Fourier transform, which sends the space C ∞ (B) of smooth functions over the closed unit ball B into F , we show C ∞ (B) is also tame; at last, thanks to Nash's embedding theorem, we conclude that for any compact riemannian manifold M, the space C ∞ (M ) is also tame.

... Lemma. Let (X, µ) be a measure space, and let w :X→ R be a positive weight function. For any map f ∈ L (µ), we set f n := e nw(x ) | f (x )| dµ (x ). Then,

F := f ∈ L (µ)      ∀ n ∈ N, f n < ∞ is a tame space.
Proof. For any k ∈ N, let

X k := { x ∈ X | k ≤ w (x ) < k +} ,
and dene

L :        F → Σ(L (µ)) f → (1 X k f ) k ∈N and K :        Σ(L (µ)) → F ( f k ) k ∈N → f k 1 X k .
Then, for any n ≥ , as w (x ) ≥ k for x ∈ X k ,

1 X k f L ≤ e -kn Xe nw(x ) 1 X k (x )| f (x )| dµ (x ).
This implies

Lf n = ∞ k= e kn 1 X k f L ≤ X e nw(x ) | f (x )| dµ (x ) ≤ f n , so L is a tame linear map. Conversely, K (( f k ) k ∈N ) n = X e nw(x ) ∞ k= 1 X k (x )| f k (x )| dµ (x ) ≤ ∞ k= X k e n(k+) | f k (x )| dµ (x ) ≤ e n k= e kn f k L ≤ C n ( f k ) k ∈N n , so K is also tame linear. Since K • L = Id F , we conclude F is a tame space. ... Lemma. Let B be the closed unit ball in R d . Then C ∞ (B) := f ∈ C ∞ c    supp f ⊂ B
is a tame space, if endowed with

f n := max |α |≤n sup x ∈B D α f (x ) , Proof. Let w (x ) = ln(+|x | ). Then, if f ∈ C ∞ (B)
and f denotes the Fourier transform of f , we have

e nw(x ) | f (x )| dx = (+|x | ) n/ | f (x )| dx .
Notice, however, that for any α ∈ N d ,

|x α || f (x )| = π e -i π ξ |x D α f (ξ ) dξ ≤ |B| π f |α | ,
and therefore, for any m ∈ N,

(+|x | ) m | f (x )|≤C m f m .
Thus,

e nw(x ) | f (x )| dx ≤ (+|x | ) (d++n) / (+|x | ) (d+) / | f (x )| dx ≤ C (d++n) / f (d++n) / (+|x | ) (d+) / dx ≤ C n f n+d+ .
This proves that the Fourier transform F : C ∞ (B) → F is tame, if F stands for the tame space introduced in lemma .. on the previous page. Conversely, if u ∈ F and

α ∈ N d , D α û (ξ ) = (-iπx ) α u (x )e -i π ξ |x dx ≤ C α (+|x | ) |α | / |u (x )| dx ≤ C α u |α | ,
and this proves F -u n ≤ C n u n .A sF is a tame space, C ∞ (B) is also tame. . The Knothe-Rosenbla rearrangement ... As we have seen in section ., if µ and ν are Borel probability measures on R, with µ atomless, and F and G are their respective cumulative distributions, then G -• F sends µ onto ν . In greater dimensions, the Knothe-Rosenblatt rearrangement is a mapping that intends to use this result to send a measure onto an other. To work with unidimensional measures, we rst need to disintegrate them both.

... Disintegration of a measure. Let X = R or X = T . Any Borel measure µ on X d can then be disintegrated according to the axes: there exists a family {µ ,...,µ d },

with µ k :X k -→P(X) Borel, such that, for all ξ ∈ C b (X d ), ξ (x ) dµ (x ) = ••• ξ (x ) dµ d x ,...,x d -(x d ) •••dµ x (x ) dµ (x ).
For the sake of clarity, let us now assume d = . If µ is absolutely continuous, and f stand for its density, then the disintegrated measures µ , µ

x also have densities, namely: In dimension two, the rearrangement is dened as follows: Let µ and ν be two absolutely continuous measures on X , with X = R or X = T . Let {µ , µ } and {ν , ν } be their disintegrations, and let F , F

f (x ) := f (x , x ) dx and f x (x ) := f (x , x ) f (x ) .
x and G , G be the cumulative distributions of µ , µ

x and ν , ν . Then, we set

T K (x ) := G -• F (x ), T K (x , x ) := G T K (x ) - • F x (x ),
and

T K := (T K , T K ).
The same procedure can be applied in any dimension.

... Lemma. The rearrangement T K thus dened maps µ onto ν.

Proof. We give a proof only for d = . Let ξ ∈ C (X ). Then,

ξ (T K (x )) dµ (x ) = ξ T K (x ), T K (x , x ) dµ x (x ) dµ (x ) = ξ (T K (x ), ) dν T K (x ) ( ) dµ (x ), for T K (x , x ) sends µ x onto ν T K (x ) . Likewise, as T K sends µ onto ν , we get ξ (T K (x )) dµ (x ) = ξ ( , ) dν ( ) dν ( ).
Brenier's map turned out to be more suited to deal with the isoperimetric inequality than Knothe's rearrangement: Alessio Figalli, Francesco Maggi, and Aldo Pratelli [, ] were able to obtain a sharp inequality using Optimal Transport.

... The starting point of our investigation is the proof, by Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio [], that this "rearrangement" is the limit of Brenier's map when the quadratic cost degenerates. We have seen in section . that, if µ and ν are probability measures on T d with strictly positive densities, and

A t :=                     λ t . . . λ t •••λ d - t                     with λ k : R → [, +∞
) such that λ k t = only for t = , then, for any t > , there is a unique optimal transport map T t between µ and ν for the quadratic cost c t induced by A t , i.e.

c t (x , ) := inf k ∈Z d A t (x --k ) = d k= λ t •••λ k - t d(x k , k ) ,
with d the usual distance on T .

... T (Carlier-Galichon-Santambrogio). When t tends to zero, the map T t converges in L (µ) to the Knothe-Rosenblatt rearrangement.

Proof. As the proof is much easier for d = , we give a proof for d = to account for the additional diculty in greater dimensions. We therefore work on the torus T , and proceed in steps.

. Let γ t := (Id, T t ) # µ be the optimal transport plan for the quadratic cost c t , and let γ K := (Id, T K ) # µ be the plan corresponding to the rearrangement. Up to a subsequence, γ t converges narrowly to some γ ∈ Γ(µ, ν ). On the one hand, γ t is optimal for c t , so

       d(x , ) + •••+ k <d λ k t d(x d , d )        dγ t (x , ) ≤        d(x , ) + •••+ k <d λ k t d(x d , d )        dγ K (x , ). (...a)
On the other hand, d(x , ) dγ (x , ) = lim t→ d(x , ) dγ t (x , ).

Therefore, taking the limit,

d (x , ) dγ (x , ) ≤ d (x , ) dγ K (x , ).
Thus, denoting by X k and Y k the projectors, we can say γ := (X , Y ) # γ is optimal between the rst marginals of µ and ν . Let µ and ν be those rst marginals; then γ

is equal to γ K := (X , Y ) # γ K = (Id, T K ) # µ . . Since inequality (...a) and the optimality of γ = (X , Y ) # γ K imply d(x , ) dγ K (x , ) + λ t        d(x , ) + •••+ <k <d λ k t d(x d , d )        dγ t (x , ) ≤ c t (x , ) dγ K (x , ),
we also have

d(x , ) dγ (x , ) ≤ d(x , ) dγ K (x , ). (...b)
We now disintegrate γ , := ((X , X ), (Y , Y )) # γ :

T ξ dγ , = ξ (x , ) dγ x , (x , ) dγ (x , ).
Let us, for a moment, assume that for γ -almost all (x , ), the marginals of γ x , are µ

x and ν . Then, by the very denition of the rearrangement

T K , since γ = γ K , for γ -almost every pair (x , ), d(x , ) d γ K x , (x , ) ≤ d(x , ) dγ x , (x , ). (...c)
If we then integrate this with respect to γ = γ K , we get

T d(x , ) dγ K (x , ) ≤ T d(x , ) dγ , (x , ).
But we have just seen the converse inequality, given by equation (...b). This is only possible if, γ -almost everywhere, there is equality in (...c). Therefore for γ -almost all (x , ), the measure γ x , is also optimal. Thus, γ , = ((X , X ), (Y , Y )) # γ K . . We must still prove the marginals of γ

x , are µ x and ν , at least almost everywhere for γ . Since the measure γ = γ K is concentrated on the graph = T K (x ), and µ is absolutely continuous, all there is to check is that

[X ] # γ x ,T K (x ) = µ x and [Y ] # γ x ,T K (x ) = ν T K (x ) ,
for almost every x .Asν is absolutely continuous, T K is a bijection; denoting by S its inverse, the second equality can be replaced with

[Y ] # γ S ( ) , = ν
which should stand for almost every . By symmetry, we thus need to check only one of the two-for instance, that for almost every x , for any continuous function

ξ = ξ (x ), ξ (x ) dγ x ,T K (x ) (x ) = ξ (x ) dµ x (x ).
Equivalently, we need only to show that for all η = η(x ) belonging to a proper countable subset of continuous functions, for all ξ = ξ (x ), η(x )ξ (x ) dγ

x ,T

K (x ) dµ (x ) = η (x )ξ (x ) dµ x dµ (x ).
It is now clear why the conclusion should holds, since η(x )ξ (x ) dγ

x ,T K (x ) (x ) dµ (x ) = η(x )ξ (x ) dγ (x , ).
. We now proceed with the third component. Let γ , t be an optimal transport plan between (X , X ) # µ and (Y , Y ) # ν for the cost

c , t = |x -| + λ t |x -| .
Then, if p x ,x , , denotes an optimal plan between µ

x ,x and ν , , we dene a transport plan

π t ∈ Γ(µ, ν ) by setting ξ (x , ) dπ t (x , ) = ξ (x , ) dp x ,x , , (x , ) dγ , t (x , x , , ). Now, T c , t dγ , t + λ t λ t T |x -| dγ t (x , ) ≤ T c t dγ t ≤ T c t dπ t ,
and

T c t dπ t = T c , t dγ , t + λ t λ t |x -| dp(x , ) dγ t = T c , t dγ , t +λ t λ t T W (µ x ,x , ν , ) dγ t (x , x , , ).
Thus,

T |x -| dγ t (x , ) ≤ T W (µ x ,x , ν , ) dγ , t (x , x , , ).
Let us, for an instant, assume

|x -| dγ (x , ) ≤ W (µ x ,x , ν , ) dγ , (x , ). (...d)
We then disintegrate γ with respect to γ

, = ((X , X ), (Y , Y )) # γ , so that ξ (x , ) dγ (x , ) = ξ (x , ) dγ x ,x , , (x , ) dγ , (x , x , , ).
Then, assuming γ x ,x , , ∈ Γ(µ x ,x , ν , ), for any x , x , , ,

W (µ x ,x , ν , ) ≤ |x -| dγ x ,x , , (x , ).
Thus, (...d) implies there must be equality for γ , -almost every x , x , , . This, in turn, means γ is optimal almost everywhere, and thus γ = γ K .

. We therefore need to prove γ x ,x , , ∈ Γ(µ x ,x , ν , ). This is done as previously (see the rd step).

. We must still prove (...d). Let ε > . Since (x , x ) → µ

x ,x and ( , ) → ν

, are measurable, according to Lusin's theorem there is a compact K of T such that µ (K ) >ε and ν (K ) >ε, and

       K × K →P (T ) (x , x ) → µ x ,x and
       K × K →P (T ) ( , ) → ν , are continuous.
We now extend those two maps into two continuous maps μ and ν on T , such that

μ = µ and ν = ν on K × K. Then, T W ( μ , ν ) dγ , t → T W ( μ , ν ) dγ , .
On the other hand, since W is bounded on P (T ),

T W ( μ , ν ) dγ , t - T W (µ , ν ) dγ , t ≤ Cγ t (T \ K × K ) and γ t (T \ K × K ) ≤ γ t K × T + γ t T × K ≤ µ K + ν K ≤ ε.
For the same reason,

T W ( μ , ν ) dγ , - T W (µ , ν ) dγ , t ≤ Cε as well. Thus, T W (µ , ν ) dγ , t → T W (µ , ν ) dγ , . . At last, d(T t (x ), T K (x )) dµ (x ) = d(, T K (x )) dγ t (x , ) -→ d(, T K (x )) dγ K (x , ) = .
and this shows T t converges to T K in L .

. A PDE for positive times ... We know from the theorem of Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio ( §.., on page ) that there is a link between Knothe's rearrangement and Brenier's map for very degenerate costs. Before investigating this relationship any further, we will now examine the dependency of the optimal map on the quadratic cost.

According to proposition .. on page , given two smooth, positive measures on T d , for any cost matrix A ∈S ++ d , there is a smooth Kantorovich potential Ψ A : T d → R. What can we say of the regularity about Ψ : A → Ψ A ? Since the optimal map

x → x -A -∇Ψ A (x ) sends one measure onto the other, we know that a Monge-Ampère equation is satised: denoting by f and the densities, we have

f (x ) = x -A -∇Ψ A (x ) det I -A -∇ Ψ A .
Thus, to get any regularity of Ψ A with respect to A, the implicit function theorem seems a good idea. We therefore set

F (A, u) := f - Id -A -∇u det I -A -∇ u ,
and intend to show D u F (A, Ψ A ) is an isomorphism.

... Zero-mean-value functional spaces. Since the potential is uniquely determined up to an additive constant, it seems more appropriate to work only with maps with zero mean values. Likewise, F obviously takes it values in a space of zero-meanvalue maps. To be of zero mean value is thus a property we shall meet very often;

there is hence a need for a specic notation. Given any functional space X, we will denote the space formed by the elements of X having a zero mean value with a subscript-for instance, C will be the space of all u ∈ C such that u = .

... Lemma. For any Proof. This follows from proposition .. on page and the characterization given by lemma .. on page .

A ∈S ++ d , if u ∈ C (T d ) is such that A -∇ u > , then F (u, A) = if
... Lemma. The operator F is smooth. For any

A ∈S ++ d , if u ∈ C (T d ) is such that A -∇ u > , and ∈ C (T ), then D u F (A, u) = div ( f -F(A, u)) A -∇ u -∇ = det A div Id -A -∇u Co A -∇ u * ∇ .
We denote by M * the transposed matrix of M, and by Co M its cofactor matrixthat is, the matrix formed by the cofactors (rst minors).

Proof. The smoothness of F is clear. By substitution, for any

ξ ∈ C ∞ , ξ x -A -∇u (x ) f (x ) -F(A, u)(x ) dx = ξ ()() d.
Therefore, if we conveniently set T A u (x ) := x -A -∇u (x ) and dierentiate the previous equation with respect to u along the direction , we get

- ∇ξ (T A u) A -∇ ( f -F(A, u)) - ξ (T A u)D u F (A, u) = . Since ∇[ξ • T A u] = [∇T A u] * ∇ξ (T A u), ∇ξ (T A u) A -∇ = ∇[ξ • T A u] [∇T A u] -A -∇ = ∇[ξ • T A u] [I d -A -∇ u] -A -∇ ,
and this yields ξ

(T A u)D u F (A, ψ A ) = ξ (T A u) div ( f -F(A, u)) [I d -A -∇ u] -A -∇ .
Therefore, as ξ •T A u is arbitrary, we get the rst equality. Then, the second expression quickly follows, thanks to the formula

M -= [Co M] * / det(M ). ... Lemma. Let ε > and A ∈S ++ d . If u ∈ C (T d ) is such that A -∇ u > ε (det A) /d -I d , then for any q ∈ [H (T d )] * , there is a unique ∈ H (T d ) such that D u F (A, u) = q. (...a)
Moreover, H ≤ C ε q (H ) * , and the constant C ε does not depend upon u.

Proof. Since A -∇ u > ε (det A) /(d -) I d , the lowest eigenvalue of Co (A -∇ u) is bounded by ε d -det A. Since > δ for some δ > , for any ξ ∈ C ∞ (T d ), ε d -det A ∇ξ ≤ [Co (A -∇ u)] * ∇ξ ∇ξ ≤ δ Id -A -∇u [Co (A -∇ u)] * ∇ξ ∇ξ ,
and thus

|∇ξ | ≤- δε d - ξ D u F (A, u)ξ . (...b)
Therefore, thanks to the existence of a Poincaré inequality for H (T d ), the map (ξ , η) → ηD u F (A, u)ξ induces a coercive, continuous bilinear form on H . We are thus entitled to apply the Lax-Milgram theorem, which yields the existence and the uniqueness, for every q ∈ (H ) * , of a ∈ H satisfying (...a). Moreover, (...b) immediately gives us H ≤ δε d -q (H ) * .

... Lemma. With the same assumptions and notations as in lemma .., for any

n ≥ , if u ∈ C n+ and q ∈ H n - satisfy u C + q (H ) * ≤ M, then ∈ H n+
, and

H n+ ≤ C ε ,M ,n q H n -+ u C n+ . (...a)
Proof. We proceed by induction. Let n ≥ , u ∈ C n+ , and q ∈ H n such that

A -∇ u > ε (det A) /(d -) I d and u C + q (H ) * ≤ M.
Let us assume we already know the solution is in H n , and that

H n ≤ C ε ,M ,n - q H n -+ u C n+ . (...b)
(We do have such an inequality for n = , according to the previous lemma, but with q (H ) * instead of q H -.) Let us now show it implies ∈ H n+ and

H n+ ≤ C ε ,M ,n q H n -+ u C n+ .
First, we set B A u := ( f -F(A, u))[A -∇ u] -, so that (...a) now reads

D u F (A, u) = div(B A u∇) = q. (...c)
Next, for h ∈ R d and ξ ∈ H , we dene

τ h ξ (x ) := ξ (x + h) and δ h ξ (x ) := ξ (x + h) -ξ (x ) h . Then, δ h (ηξ ) = ηδ h ξ + (δ h η)τ h ξ , and δ h ξ L ≤ ξ H . Let ν ∈ N d be a d-index, with |ν | := ν + •••+ ν d = n -, and assume h ∈ R d is
small enough. We can apply the operator δ h to (...c), and thus obtain

div(B A u∇δ h ) = δ h q -div [(δ h B A u)∇τ h ]
Then, by applying

∂ ν = ∂ |ν | /∂x ν •••∂x ν d d , we get div(B A u∇δ h ∂ ν ) = δ h ∂ ν q - ≤α ≤ν ν α div [(δ h ∂ ν -α B A u) ∇τ h ∂ α ] - ≤α <ν ν α div [(∂ ν -α B A u) ∇δ h ∂ α ] . (...d)
According to lemma .. on page , this implies

δ h ∂ ν H ≤ C ε δ h ∂ ν q (H ) * + C ε ≤α ≤ν ν α div [(δ h ∂ ν -α B A u) ∇τ h ∂ α ] (H ) * + C ε ≤α <ν ν α div [(∂ ν -α B A u) ∇δ h ∂ α ] (H ) * .
Since δ h ∂ ν q (H ) * ≤∂ ν q L , this bound is uniform in h. Therefore, ∈ H n+ and

H n+ ≤ C        q H n -+ ≤k ≤n - (+u C n -k+ ) H k+        . (...e)
When n > , the following inequalities hold:

u C n -k+ ≤ C k ,n u -k n - C u k n - C n+ , H k+ ≤ C k ,n k n - H -k n - H n .
These are Landau-Kolmogorov inequalities; we have already met them in lemma .. on page . They can be easily proved by induction from

ξ C ≤ ξ C ξ C and ξ H ≤ ξ L ξ H , for ξ smooth enough satisfying ξ = . Still, since a -t b t ≤ ( -t )a + tb, we get u C n -k+ H k+ ≤ k n - u C H n + - k n - u C n+ H ,
and therefore

H n+ ≤ C q H n -+ +u C H n + u C n+ H .
This last inequality also holds when n = , thanks to (...e).As H ≤ C ε q H - and u C + q H -≤ M, using our assumption (...b) we get

H n+ ≤ C ε ,M ,n q H n -+ u C n+ .
... Lemma. Let α ∈ (, ). For any u ∈ C n+,α with A -∇ u > , and any

q ∈ C n ,α (T d ), there is a unique ∈ C n+,α (T d ) such that D u F (A, u) = q. Proof. If q ∈ C n ,α
, then q ∈ H n , and thus according to lemma .. on page , there is ∈ H n+ such that D u F (A, u) = q in [H ] * . But since q = , such an equality in fact holds in H -. Thus, locally, in a weak sense, D u F (A, u) = q. Then, since u ∈ C n+,α , the coecients of the operator D u F (A, u) are C ,α ; this implies ∈ C n+,α (see for instance the monograph by David Gilbarg and Neil S. Trudinger [, Theorem . and . and .]).

... T. For any A ∈S ++ d , let Ψ A be the Kantorovich potential between the probability measures µ and ν , which are assumed to have smooth, strictly positive densities. Then, for any n ≥ and α ∈ (, ), the map

Ψ :        S ++ d -→ C n+,α (T d ) A -→ Ψ A is C .
Proof. Let us denote by Ω be the set of all (A, u)

∈S ++ d × C n+,α (T d ) such that A -∇ u > . Then Ω is open, the operator F : Ω → C n ,α (T d ), dened by F (A, u) := f - Id -A -∇u det I -A -∇ u ,
is smooth and, according to lemma .. on the preceding page,

D u F (A, ψ A ) : C n+,α (T d ) → C n ,α (T d )
is a bijection. From the Banach-Schauder theorem, we infer it is an isomorphism.

Since F (A, Ψ A ) = , according to the implicit function theorem, there is a C map Φ such that, for any (u, B) ∈ U , we can have F (B, u) = if and only if u = Φ B .

According to lemma .. on page , necessarily then

Φ B = Ψ B . Thus, Ψ = Φ is a C map S ++ d → C n+,α (T d ).
... We are now going to apply this result to a cost c t dened by

c t (x , ) := d(x , ) + λ t d(x , ) + •••+ λ t •••λ d - t d(x d , d ) ,
that is, a cost induced by the diagonal matrix A t := diag(, λ t , λ t λ t ,..., λ i t ).W e assume λ ,...,λ d -: R → [, +∞) are smooth, with λ k t = if and only if t = . For now, we are only interested in positive times. The behavior when t = will be studied in the next section.

... P. The map ψ : t → Ψ A t is C on (, +∞), and satises:

div f A t -∇ ψ t - ∇ ψt -Ȧt A - t ∇ψ t = . (...a) Moreover, if u : (, +∞) → C n+,α (T d ) is C and satises A t -∇ u > and div f A t -∇ u t - ∇ ut -Ȧt A - t ∇u t = (...b)
for all t ∈ (, +∞), and u t = ψ t for some t > , then u t = ψ t for any t > .

Proof. If ψ t := Ψ A t , then F (A t , ψ t ) = for all t > . If we dierentiate with respect to t, we get

D u F (A t , ψ t ) ψt +D A F (A t , ψ t ) Ȧt = .
On the one hand, it follows from lemma .. on page that

D u F (A t , ψ t ) ψt = div f A t -∇ ψ t -∇ ψt .
On the other hand, a direct computation yields

D A F (A t , ψ t ) Ȧt = -div f A t -∇ ψ t -Ȧt A -∇ψ t .
We thus get (...a).

Conversely, if u : (, +∞) → C n+,α (T d ) is C and satises (...b), with u t = ψ t for some t > , then F (A t , u t ) must be constant and equal to F (A t , u t ) = .

Thus, according to lemma .. on page , u t = Ψ A t for all times.

. Initial condition in two dimensions ... Due to the very technical nature of the proofs in this section we will only deal with the dimension . Then, in section ., we shall explain what changes in higher dimensions.

... Let λ : R → [, +∞) be a smooth function such that λ t = if and only if t = .

From now on, we will only consider the cost induced by

A t :=        λ t        , which is c t (x , ) := d(x , ) + λ t d(x , ) .
For t nonzero, let ψ t be the associated Kantorovich potential between the probability measures µ and ν . We assume they have the same properties as before-that is, they are absolutely continuous with strictly positive, smooth densities. Let T t be the corresponding optimal transport map. Then, according to proposition .. on the preceding page, t → ψ t and t → T t are C on R \{}. Moreover, we know from the theorem of Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio (page ),

Chapter . From Knothe's rearrangement to Brenier's map that, as t tends to zero, the map T t converges to the Knothe-Rosenblatt rearrangement R in L (µ).

... Potentials for Knothe's map. By construction, the Knothe-Rosenblatt rearrangement can be written as

T K (x , x ) = (T K (x ), T K (x , x ))
, where x → T K (x ) is the optimal map between µ and ν , and x → T K (x , x ) is the optimal map between µ

x and ν T K (x ) . Recall {µ , µ } and {ν , ν } are the disintegrations of, respectively, µ and ν (denition .. on page ). Thus, there must exist Kantorovich potentials

x → ϕ (x ) and x → ϕ (x , x ) such that T K (x ) = x -∂ ϕ (x ), T K (x , x ) = x -∂ ϕ (x , x ).
Those potentials are normalized so that ϕ (x ) dx = , and ϕ (x , x ) dx = for almost all x .

... As t tends to zero, the optimal map

T t = Id -(∂ ψ t ,∂ ψ t /λ t ) converges toward T K = Id -(∂ ϕ ,∂ ϕ ). A rst-order expansion might therefore be ∂ ψ t ∼ λ t ∂ ϕ .
Since ϕ does not depend on x , we could simply have ψ t ∼ ϕ + λ t ϕ . This leads us to a priori write:

ψ t (x , x ) = ψ t (x ) + λ t ψ t (x , x ), with ψ t (x ) := ψ t (x , x ) dx and ψ t (x ) := λ t ψ t (x ) -ψ t (x ) .
Thus, ψ t (x ) dx = and ψ t (x , x ) dx = .

Such a decomposition allows us to extend our analysis up to t = .

... Notations. Let us denote by E the set of all (t , u , u

) ∈ R × C ∞ (T ) × C ∞ (T ) such that u (x ) dx = and u (x , x ) dx = ,
and by Ω the open subset of E formed by the tuples (t , u , u ) such that:

• either t , and then A t -∇ (u + λ t u ) > ;

• or t = , and then -∂ , u > and -∂ , u > . Next, we dene an operator G : Ω → C ∞ (T ). When t is nonzero,

G(t , u , u ) := F (A t , u + λ t u ), (...a)
where F is the operator introduced in section .:

F (A, u) = f - Id -A -∇u det I -A -∇ u .
We then extend G to include the case t = ; indeed, notice Proof. As u , u are uniquely determined by the values of u t := u + λ t u , thanks to the formulae

A -∇(u + λ t u ) =        ∂ u + λ t ∂ u ∂ u        and A -∇ (u + λ t u ) =        ∂ , u + λ t ∂ , u λ t ∂ , u ∂ , u ∂ , u        .
u (x ) := u t (x , x ) dx and u (x ) := λ t u t (x ) -u (x ) ,
the lemma follows directly from lemma .. on page .

... Alas, the continuity method here seems to fail us: we cannot do the same as in the previous section and apply the implicit function theorem, for if we solve D u G(, ψ , ψ )( , ) = q, then a priori the solution is not smooth enough. Indeed, as we will see later, if q ∈ H n , then ∈ H n+ , but we can only get ∈ H n . We can, however, bypass this diculty by considering C ∞ functions, so as to have an innite source of smoothness, and use the Nash-Moser implicit function theorem ( §.., on page ) instead of the usual implicit function theorem.

... We need only to use this theorem in a neighborhood of (, ψ , ψ ) ∈ Ω. Let us dene this neighborhood, which we denote by Ω , in the following way: rst, take

ε > such that -∂ , ψ > ε and -∂ , ψ > ε; then, dene Ω as the set of all (t , u t , u t ) ∈ Ω such that: if t = , then        -∂ , u > ε -∂ , u > ε , (...a) if t , then        -∂ , u -λ t ∂ , u > ε A t -∇ (u + λ t u ) > ελ / t I . (...b)
... Zero mean value w.r.t. the nd variable. Recall that we denote with a subscript the sets of maps with zero mean value: C ∞ is thus the set formed by the smooth functions u such that u = . When dealing with a space of functions with two variables, we also denote by a " * , " subscript, as in C ∞ * , (T ) the set formed by the ξ such that ξ (•, x ) dx = .

... T. For all (t , u , u ) ∈ Ω , for any q ∈ C ∞ (T ), there is a unique

( , ) ∈ C ∞ (T ) × C ∞ * , (T ) such that D u G(t , u , u )( , ) = q, (...a)
Moreover, the inverse operator

S :        Ω × C ∞ (T ) → C ∞ (T ) × C ∞ * , (T ) (t , u , u ), q → ( , ) is smooth tame.
See denition .. on page for the precise denition of a smooth tame map.

Proof. We report the proof of the existence of ( , ) and of the following "tame" estimate

H n+ + ∂ H n ≤ C n u C n+ + u C n+ + q H n ,
to the next two subsections. Let us conclude from that point on. Then, all that remains to show is that S is continuous, and that al the derivatives D k S are tame.

First, if (t k , u k , u k , q k ) ∈ Ω converges toward (t , u , u , q) ∈ Ω , for each k let ( k ,
k ) be the corresponding inverse. Thanks to the tame estimate (which we have not proved yet), k and k are bounded in all the spaces H n . Hence, compact embeddings provide convergence, up to an extraction, to some , as strongly as we want, which, as DG is continuous, must be the solution of DG(t , u , u )( , ) = q.

Then, all the derivative D k S are also tame, since they give the solution to the same kind of equation as (...a). Indeed, by dierentiating (...a), we get

D u G DS = Dq -D(D u G)S. ... C. The map        R → C ∞ (T ) × C ∞ * , (T ) t → (ψ t , ψ t )
is smooth.

Proof. On some interval (-τ , τ ), this is a direct consequence of corollary .. on page , theorem .. on the preceding page, and lemma .. on page . For larger t, it follows from theorem .. on page .

... T. The curve formed by the Kantorovich potentials (ψ t ) is the only curve in C (T ) dened on R such that, for t ,

A t -∇ ψ t > and div f A t -∇ ψ t - ∇ ψt -Ȧt A - t ∇ψ t = , (...a)
and that can be decomposed into two smooth curves (ψ t ) and (ψ t ) such that

ψ t (x , x ) = ψ t (x ) + λ t ψ t (x , x ),
with ψ and ψ the Kantorovich potentials for the Knothe rearrangement.

Proof. Let u t = u t + λ t u t be such a curve, and let us check that u t = ψ t . Since u and u are the potentials for the Knothe rearrangement, (, u , u ) ∈ Ω , so (t , u t , u t ) is in Ω at least for t small. For t ,(...a) is equivalent to

D u F (t , u t ) ut +D t F (t , u t ) = ,
and therefore

D u G(t , u t , u t )(u t , u t ) +D t G(t , u t , u t ) = .
By assumption, G(, u , u ) = . Integrating in time, we get G(t , u t , u t ) = . Therefore, according to lemma .. on page , we have u t = ψ t and u t = ψ t , i.e. u t = ψ t . For larger t's, we apply proposition .. on page .

Proof of the invertibility

... Let us recall F (A, u) = f - Id -A -∇u det I -A -∇ u , and
G(t , u , u ) := F (A t , u + λ t u ) with A t :=        λ t        . (...a)
We want to prove the invertibility of D u G(t , u , u ). The rst lemma ( §.., on the current page) will consider the case t , the second ( §.., on the following page) the case t = .

... Lemma. For any (t , u , u ) ∈ Ω with t , for all q ∈ C ∞ (T ), there is a unique ( ,

) ∈ C ∞ (T ) × C ∞ * , (T ) such that D u G(t , u , u )( , ) = q. (...a)
Proof. If we set u t := u + λ t u , then lemma .. on page tells us that there is a unique

t ∈ C ∞ (T ) such that div f -G(t , u , u ) I -A - t ∇ u t - A - t ∇ t = q. (...b) Let us dene (x ) := t (x , x ) dx and (x , x ) := λ t t (x , x ) -(x ) .
Then, by construction, ( , ) is the unique pair solving (...a).

... Lemma. For any (, u , u ) ∈ Ω , for all q ∈ C ∞ (T ), there is a unique

( , ) ∈ C ∞ (T ) × C ∞ * , (T ) such that D u G(, u , u )( , ) = q.
Proof. By substitution, for any ξ ∈ C ∞ , from (...b) we get

ξ (x -∂u (x )) f (x ) -G(, u , u )(x ) dx = ξ ()() d,
with ∂u := (∂ u ,∂ u ). Therefore, if we dierentiate this with respect to u along the direction , we get

- ∇ξ (Id -∂u) ∂ f -G(, u , u ) - ξ (Id -∂u)D u G(, u , u )( , ) = .
Since ∇[ξ • (Id -∂u)] = [I -D∂u] * ∇ξ (Id -∂u), we have

∇ξ (Id -∂u) ∂ = ∇[ξ • (Id -∂u)] [I -D∂u] -∂
and this yields

D u G(, u , u )( , ) = div f -G(, u , u ) [I -D∂u] -∂ . Notice, then, f -G(, u , u ) [I -D∂u] - = (Id -∂u)        -∂ , u ∂ , u -∂ , u        .
Thus,

D u G(, u , u )( , ) = ∂ (x -∂u (x )) -∂ , u (x ) ∂ (x ) + ∂ ......... . Therefore, if D u G(, u , u )( , ) = q, integrating with respect to x yields ∂ (x -∂u (x )) -∂ , u (x ) ∂ (x ) dx = q(x ) dx ,
which then brings about

∂ (x -∂u (x )) -∂ , u (x ) dx ∂ (x ) = q(x ) dx . (...a) As q(x ) dx = , there is a smooth Q : T → R such that ∂ Q (x ) = q(x , x
) dx , and it is unique if we require Q () = . Thus, taking a primitive of (...a),w e obtain

(x -∂u (x )) -∂ , u (x ) dx G (x ) ∂ (x ) = Q (x ) + c , for some c ∈ R. Since G (x ) > , we get ∂ = Q + c G ,
and this yields the unique possible value for c, since the integral with respect to x of the right hand side must be zero. Combined with the condition dx = , we thus have completely characterized . Now, let us do the same for . We have to solve the equation

∂ (Id -∂u) -∂ , u ∂ = q -∂ (Id -∂u) -∂ , u ∂ -∂ (Id -∂u) ∂ , u ∂ ,
and this is exactly the same kind of equation as (...a). If we x x ∈ T , the same reasoning can be applied , and in this way we get as well.

Proof of the tame estimates ... We refer to denition .. on page for a precise denition of what a tame estimate is. Basically, our aim here is to show that, locally on (t , u , u ) ∈ Ω and q ∈ C ∞ (T ), for any n ∈ N, there is a constant C n > such that, if

D u G(t , u , u )( , ) = q (...a) for some ( , ) ∈ C ∞ (T ) × C ∞ * , (T ), then H n+ + H n ≤ C n +|t | + u H n+ + u H n+ + q H n .
In fact, we will prove something slightly stronger:

H n+ + ∂ H n ≤ C n u C n+ + u C n+ + q H n . (...b)
Indeed, as (x , x ) dx = , a Poincaré inequality implies

H n ≤ c n ∂ H n .
Notice also that (...b) would by itself yields uniqueness in lemma .. on page .

... We start with the case t . As the bound for H n+ simply follows from lemma .. on page and an integration with respect to x , we just have to nd a bound for ∂ H n . Let us begin with ∂ L ; we will then proceed by induction.

... Lemma. Let M , ε > . There is a constant C, which depends on M and ε, such that, for any (t , u , u ) ∈ Ω with t and for all q ∈ C ∞ (T ) satisfying

q L + u C + u C ≤ M , (...a) if ( , ) ∈ C ∞ (T ) × C ∞ (T ) is a solution of (...a), then ∂ L ≤ C. (...b)
Proof. We set u t := u t + λ t u t and t := t + λ t t . Then, D u F (A t , u t ) t = q, and (...b) in the denition of Ω ensures we an apply lemma .. on page and get

t H ≤ C ε ,M , q L + u t C ≤ C. (...c)
We now set

B t := f -G(t , u , u ) I -A - t ∇ u t - A - t = f -G(t , u , u ) det(A t -∇ u t ) Co (A t -∇ u t ) * = (Id -A - t ∇u t ) det A t Co (A t -∇ u t ) *
so that, according to (...a) and lemma .. on page ,(...a) becomes div(B t ∇ t ) = q.

Notice det A t = λ t and

Co (A t -∇ u t ) =        λ t -λ t ∂ , u λ t ∂ , u t λ t ∂ , u t -∂ , u t        .
Therefore, we can write

B t = U t + V t /λ t (...d) with U t := (Id -A - t ∇u t )        -∂ , u ∂ , u ∂ , u        , (...e) V t := (Id -A - t ∇u t )        -∂ , u t        . (...f) Thus, q = div(B t ∇ t ) = div(U t ∇ t ) + λ t div(V t ∇ t ).
As ∂ = , we have V t ∇ = . Since t = + λ t , we get

div(U t ∇ t ) + div(V t ∇ ) = q,
that is,

∂ (Id -A - t ∇u t )( -∂ , u t )∂ = q -div(U t ∇ t ). (...g)
Since > δ for some δ , and as (...b) in the denition of Ω means -∂ , u t > ε, allowing the constant C to change from line to line we get

∂ L ≤ C δε (Id -A -∇u t )( -∂ , u t )|∂ | ≤ C q -div(U t ∇ t ) ≤ C (q L + U t ∇ t H ) L .
However,

(x , x ) dx = implies L ≤ C ∂ L . Therefore, ∂ L L ≤ C ∂ L ≤ C (q L + U t ∇ t H ) L .
Thus, since U t C ≤ C (+u C + u C ) ≤ C follows from (...e), we obtain

∂ L ≤ C q L + t H .
Then, using (...c), we get the result.

... Lemma. Under the same assumptions as in the previous lemma, for any n ∈ N,

there is a constant C n = C n (M , ε) such that ∂ H n ≤ C n q H n + u C n+ + u C n+ . ( .
∂ (Id -A -∇u t )( -∂ , u t )∂ = q -div(U t ∇ t ).
We already know from lemma .. on page that t = +λ t is smooth, therefore, if we apply

∂ ν = ∂ |ν | /∂x ν •••∂x ν d d , we get ∂ (Id -A -∇u t )( -∂ , u t )∂ ∂ ν = - ≤α <ν ν α ∂ ∂ ν -α (Id -A -∇u t )( -∂ , u t ) ∂ ∂ α + ∂ ν q -∂ ν div(U t ∇ t ).
On the other hand, since > δ and -∂ , u t > ε, we have

∂ ∂ ν L ≤ δε (Id -A -∇u t )( -∂ , u t )|∂ ∂ ν | ≤- δε ∂ (Id -A -∇u t )( -∂ , u t )∂ ∂ ν ∂ ν .
Thus,

∂ ∂ ν L ≤ ≤α <ν ν α ∂ ν -α (Id -A -∇u t )( -∂ , u t ) ∂ ∂ α ∂ ∂ ν - δε ∂ ν q -∂ ν div(U t ∇ t ) ∂ ν ,
and therefore

∂ ∂ ν L ≤ ≤α <ν C ∂ ν -α (Id -A -∇u t )( -∂ , u t ) ∂ ∂ α L ∂ ∂ ν L + C ∂ ν q -∂ ν div(U t ∇ t ) L ∂ ν L . As ∂ ν L ≤ c ∂ ∂ ν L , we get ∂ ∂ ν L ≤ C ≤k ≤n (Id -A -∇u t )( -∂ , u t ) C n+-k ∂ H k + C q H n+ + U t ∇ t H n+ . (...b)
On the one hand, we can use the same Landau-Kolmogorov inequalities as in the proof of Lemma .., and a -t b t ≤ (t )a + tb, to get, for ≤ k ≤ n, the following bound:

(Id -A -∇u t )( -∂ , u t ) C n+-k ∂ H k ≤ c n (Id -A -∇u t )( -∂ , u t ) C n+ ∂ L + (Id -A -∇u t )( -∂ , u t ) C ∂ H n .
Recall we have assumed (...a) holds true for n; therefore, using (...a), we get

(Id -A -∇u t )( -∂ , u t ) C n+-k ∂ H k ≤ c n +q H n + u C n+ + u C n+ . (...c)
On the other hand,

U t ∇ t H n+ = D n+ (U t ∇ t ) H ≤ C {U t C n+ ∇ t H + U t C ∇ t H n+ } , which, since u C + u C ≤ M, implies U t ∇ t H n+ ≤ C +u C n+ + u C n+ t H + t H n+ .
Then, using Lemma .. we get

U t ∇ t H n+ ≤ c n q H n + u C n+ + u C n+ . (...d)
Bringing together (...b), (...c), and (...d), we get the estimate we seek.

... Lemma. The result of lemma .. on page still stands when t = , with the same constants.

Proof. Let (, u , u ) ∈ Ω and q ∈ C ∞ (T ) such that

q L + u C + u C ≤ M , (...a)
Then, since (s, u , u ) ∈ Ω for s small enough, we can proceed by approximation.

Indeed, if ( s , s ) is the solution to D u G(s, u , u )( s , s ) = q, where u , u , q have been all xed, then all the H n norms of s , s are bounded according to lemma .. on page . Up to an extraction, there is convergence, which by compact embedding is as strong as we want. But the convergence can only be toward the solution of D u G(, u , u )( , ) = q, hence estimate (...a) is still valid for the limit.

. Higher dimensions ... The diculty in extending those results in higher dimension only comes from the technical nature of section .. We need a decomposition, not only of the potential, but also of the matrix eld B, extending (...d). The existence of such a decomposition is the only additional diculty.

Seing and notations

... Cost matrix. We consider d -smooth maps λ ,...,λ d -: R → [, +∞) such that λ k t = if and only if t = . We then dene

A t :=                              λ t λ t λ t . . . i <d λ i t                              .
... New decomposition of the potential. In that setting, the decomposition of the Kantorovich potential ψ t becomes

ψ t (x ,...,x d ) = ψ t (x ) + λ t ψ t (x , x ) + ...+        i <d λ i t        ψ d t (x ,...,x N ).
where ψ k t depends only on the k rst variables x ,...,x k , and is such that

∀ x ,...,x k -, ψ k t (x ,...,x k -, k ) d k = .
For convenience, we set

ψ k := ψ k + λ k ψ k+ + ...+        k ≤i <d λ i        ψ d ,
so that we may have

ψ := ψ , ψ k = ψ k + λ k ψ k+ , ψ d = ψ d ,
and

∀ x ,...,x k -, ψ k t (x ,...,x k -, k ,..., d ) d k ...d d = .
For instance, if d = ,

ψ = ψ + λ ψ + λ λ ψ and              ψ = ψ + λ ψ + λ λ ψ ψ = ψ + λ ψ ψ = ψ .
... Domain. We denote by E the set of all (t , u ,...,

u d ) ∈ R × C ∞ (T k ) such that ∀ k ∈{,...,d }, u k dx k = .
Then, if (t , u ,...,u d ) ∈ E, we set

ûd := u d , ûk := u k + λ k ûk+ , u := û .
This is consistent with the previous notation. Notice

∇u =                           ∂ û λ ∂ û λ λ ∂ û . . . λ k ∂ d ûd                           and A -∇u = ∂ û =                           ∂ û ∂ û ∂ û . . . ∂ d ûd                          
, and thus,

A -∇ u = D∂ û =                      ∂ , û ••• ∂ , û ∂ , û . . . . . . . . . . . . . . . ∂ ,d ûd ∂ ,d ûd ••• ∂ d ,d ûd                      . (...a)
We dene Ω as the open subset of E formed by the (t , u) such that:

• either t , and then A t -∇ u > ;

• or t = , and then -∂ k ,k u k > for all k. As previously, we need only to work on a neighborhood Ω of the tuple (, u , u ), with u and u the Kantorovich potentials for the Knothe-Rosenblatt rearrangement. This neighborhood will be dened later on.

Invertibility

... We want to solve, for (, u) ∈ Ω , the equation D u G(, u) = q. For t > ,

D u G(t , u) = div ( f -G(t , u)) I d -A -∇ u - A -∇ .
Replacing A -∇ u and A -∇ with D∂ û and ∂ , we get

D u G(t , u) = div ( f -G(t , u)) [I d -D∂ û] -∂ .
When t = , we have ûk = u k and ∂ û = ∂u, so this becomes

q = D u G(, u) = div ( f -G(, u)) [I d -D∂u] -∂ .
The trick is to integrate with respect to x k+ ,...,x d to get an equation on ,..., k .

If ,..., k -have already been found, [I d -D∂u] -being lower triangular thanks to (...a), the resulting equation on k is of the same kind as the one we have dealt with in lemma .. on page . The same reasoning can thus be applied.

Tame estimate

... As in the two-dimensional case, we need only to nd a tame estimate when t is nonzero for the solution ( ,..., d ) of

q = div(B∇) with B := (Id -A -∇u) det A Co (A -∇ u) * .
First, by integrating with respect to x d , we obtain the same problem as in dimension d -. Therefore, we can proceed by induction on d. So let us assume we already have a tame estimate for ,..., d -. To get an estimate for d = d , we will nd one for each k , this time by induction on k. Since = satises a nice strictly elliptic equation, and thus comes with a tame estimate, we need only to show how to get one for k if we have one for ,..., k -.

... The key lies in the following decomposition of the matrix B: for any k,

B = B + λ B + λ λ B + ...+ λ •••λ k -B k -+ λ •••λ k - Bk ,
where the coecients (b i α , β ) of B i are zero except when min(α , β ) = i, and where the coecients ( bk α ,β ) of Bk are zero except for min(α , β ) ≥ k :

B i =                     b i i ,i ••• b i i ,d . . . b i d ,i                     , Bk =                     bk k ,k ••• bk k ,d . . . . . . . . . bk d ,k ••• bk d ,d                     .
The point is that all the coecients b i α ,β , bk α ,β can be bounded in C n by the norms of the u i in C n+ uniformly in t, at least for small t.

... Let us assume such a decomposition exists; then,

div(B∇) =        i <k λ •••λ i -div(B i ∇)        + λ •••λ k -div( Bk ∇),
and thus, since

= + λ + ...+ λ •••λ k -k -+ λ •••λ k -k ,
with ∂ i j = if i > j and as that implies

∂ i = λ •••λ i -∂ i i , we have div(B∇) =        i <k div(B i ∇ i )        + div( Bk ∇ k ). (...a)
On the one hand, the matrix Bk is symmetric and non-negative, and we can chose the neighborhood Ω so that to ensure

∀ ξ ∈ R d , ε        i ≥k |ξ i |        ≤ Bk ξ |ξ .
On the other hand, since

∀ x ,...,x k -, ••• k (x ,...,x d ) dx k ...dx d = ,
we have a Poincaré inequality:

k L ≤ C i ≥k ∂ i k L . Therefore, k L ≤ C ε Bk ∇ k |∇ k ≤ C ε div( Bk ∇ k ) L k L ,
and this shows how we can deduce a L estimate for k from (...a) and a series of estimates for i , for i < k. Estimates for the norms H n , n > , easily follow, by the same reasoning as in lemma .. on page .

... Thus, all we need to do is to prove the existence of the following decomposition:

B = B + λ B + λ λ B + ...+ λ •••λ d -B d , with B i =                     b i i ,i ••• b i i ,d . . . b i d ,i                     . Remember B := (Id -A -∇u) det A Co (A -∇ u) * ,
and

det A = λ λ λ ••• λ •••λ d - .
Therefore, all we have to do is to show how in Co (A -∇ u) we can gather the λ k so as to get the decomposition we seek. Since

∂ i , j u = λ •••λ max (i ,j) -∂ i , j ûmax (i ,j) , Co (A -∇ u) i , j = σ ∈S d σ (i)=j ε (σ ) ≤k ≤d ki (A -∇ u) k ,σ (k ) = σ ∈S d σ (i)=j ε (σ ) ≤k ≤d ki λ •••λ max(k ,σ (k ))- δ k ,σ (k ) -∂ k ,σ (k ) ûmax(k,σ (k )) .
Thus, for i ≤ j, we set

ω α , β = λ α •••λ max(α , β ) - δ α ,β -∂ α ,β ûmax(α ,β ) . Then, Co (A -∇ u) i ,j = σ ∈S d σ (i)=j ε (σ ) ≤k ≤d ki λ •••λ k -ω k ,σ (k ) = σ ∈S d σ (i)=j ε (σ ) λ •••λ i -        ≤k ≤d λ •••λ k -                    ≤k ≤d ki ω k ,σ (k )             = det A λ •••λ i - σ ∈S d σ (i)=j ε (σ ) ≤k ≤d ki ω k ,σ (k ) .
Since we have assumed i ≤ j, this is exactly what we wanted.

. An open problem ... In this chapter, we have studied the behavior of the optimal transport map when the cost matrix degenerates. But we have done so only for a diagonal cost matrix.

It would, however, be possible to consider more general situations; for instance, we could take a cost matrix A that is diagonal in another base {u , ••• , u d }.

In dimension two, this other base can be written as

u := (cos θ , sin θ ), u := (-sin θ , cos θ ).
Then, the following matrix is diagonal in this basis:

A λ :=        cos θ -sin θ sin θ cos θ               λ               cos θ sin θ -sin θ cos θ        , that is, A λ =        (cos θ ) + λ(sin θ ) ( -λ) cos θ sin θ ( -λ) cos θ sin θλ (cos θ ) + (sin θ )        .
Let us assume θ ∈ (-π /, π /), and set χ = tan θ . Then,

A λ = (cos θ )        +λχ ( -λ) χ ( -λ) χλ + χ        .
We must then pay for each length unit we travel in the direction u , and λ in the direction u . The associated transport cost is thus

c λ (x , ) = inf k ∈Z A λ (x --k ) = inf k ∈Z u |x --k + λ u |x --k .
... If χ is rational, e.g. χ = p/q, then the situation remains basically the same. Indeed, considering our two measures as Z -periodic measures dened on R and setting Z = p + q (Zu + Zu ), we can see they are also Z -periodic. Then the results of this chapter apply verbatim on R /Z . θ u u ... But when χ is irrational, then the trajectory Ru is dense in T . As moving along that direction costs less and less as λ tends to zero, the associated cost tends to zero as well:

... P. If tan θ ∈ R \ Q, then c λ (x , ) → when λ → .
Proof. Without loss of generality, we can assume = . Then,

c λ (x , ) = inf k ∈Z u |x -k + λu |x -k = inf k ∈Z (cos θ ) (x + χx -k -χk ) + λ (x -χx -k + χx ) .
Thus, for any ε > , we can nd k ,

k such that |x + χx -k -χk | ≤ ε, because Z + χ Z is dense in R.
Then, taking λ small enough, we get c λ (x , ) ≤ ε (cos θ ) .

... On the other hand, the associated optimal transport map is bounded in L . So what are its limit points? Is there convergence?

One approach could be to study the Γ-convergence of the functionals

F λ :        Γ(µ, ν ) → [, ∞), γ → c λ (x , ) dγ (x , ).
Sadly, even though there are Γ-limit points-there always are-, to identify one of them is not trivial at all. The nature of the irrationality of χ seems to be of some importance, but that makes the problem quite complex.

For more information about Γ-convergence, we refer to Andrea Braides's book on the subject [].

The Γ in "Γ-convergence" has nothing to do with the set Γ(µ, ν )! on the other hand, were able to compute the solution using Newton's method, which is akin to a continuation method.

Chapter

. A new method ... The results exposed in chapter can eectively be applied to compute Brenier's optimal map. This section intends to show how, at least when the underlying space is the torus T and the target measure is uniform. More general cases should be within our reach, even though their implementation is a bit more complex.

... As Sigurd Angenent, Steven Haker, and Allen Tannenbaum [], we start from the Knothe-Rosenblatt rearrangement T K , which is given by two Kantorovich potentials ϕ , ϕ :

T K (x , x ) =        x -∂ ϕ (x ) x -∂ ϕ (x , x )        .
Then, as Grégoire Loeper and Francesca Rapetti [], we use a continuation method:

we rst set u = ϕ and = ϕ ; we then increase t little by little, and update u t and t in such a way that u t + t t is always the Kantorovich potential for the cost

c t (x , ) := x - + t x - .
Thus, for t = we get the Kantorovich potential for the usual quadratic cost, and at that point Brenier's map is just T B := Id -∇(u + ).

In order to update u t and t , we follow the same method as in chapter : we use the Monge-Ampère equation. Denoting by f the density of the initial measure, for any t, we should have

f = ( -∂ , u t -t ∂ , t )( -∂ , t ) -t (∂ , t ) .
Therefore, the time derivatives ut , t are given by the following linearized Monge-Ampère equation:

( -∂ , t )∂ , ut + t ( -∂ , t )∂ , t + ( -∂ , u t -t ∂ , t )∂ , t -t ∂ , t ∂ , t = (∂ , t ) -( -∂ , t )∂ , t . (...a)
This equation, with the aforementioned initial condition, can be broken down as follows: ... Lemma. Let ( ¯U n+ , ¯V n+ ) solve

       ∂ , ut (x ) = p t (x , x ) dx , div(A t ∇ t ) = q t , (...b) with        p t = det(∇ t ) + t div Co ∇ t * ∇ t , q t = det(∇ t ) -( -∂ , t )∂ , ut -∂ , t , (
       ∂ , ¯U n+ = p n dx , div A n ∇ ¯V n+ = q n , (...a)
without any further condition. Then, (...c) is satised by

Un+ := ¯U n+ - ¯U n+ dx + nh ¯V n+ dx - ¯V n+ dx dx Vn+ := ¯V n+ - ¯V n+ dx .
Proof. We set

¯U n+ := ¯U n+ - ¯U n+ dx + nh ¯V n+ dx - ¯V n+ dx dx ¯V n+ := ¯V n+ - ¯V n+ dx .
Then, if Īn+ := ¯V n+ dx , since ( ¯U n+ , ¯V n+ ) is a solution of (...a), we have

∂ , ¯U n+ = ∂ , ¯U n+ + nh∂ , Īn+ = p n dx + nh∂ , Īn+ , q n = div A n ∇ ¯V n+ = div A n ∇ ¯V n+ + div(A n ∇ Īn+ ) .
Notice that, if w is a function of x only, then

div(A n w ) = nh( -∂ , V n )(∂ , w ). Therefore, div A n ∇ U n+ = nh( -∂ , V n ) ∂ , p n div A n ∇ ¯U n+ = nh( -∂ , V n ) ∂ , p n dx + nh∂ , Īn+ div A n ∇ ¯V n+ = q n -nh( -∂ , V n ) ∂ , Īn+ .
Then, using (...b), we get

div A n ∇ ¯U n+ + nh ¯V n+ = div A n ∇ U n+ + nh V n+ .
Since A n is a positive-denite, symmetric matrix, and both ¯U n+ + nh ¯V n+ and U n+ + nh V n+ have a zero mean value, they must be equal. Then, it follows from (...c) that U n+ = ¯U n+ and V n+ = ¯V n+ .

... Thus, we obtain algorithm ., on the next page. How to compute the potentials for the Knothe-Rosenblatt rearrangement is not detailed, as it as been explained elsewhere (see §.. on page ).

.

Results

... FreeFem++. The following results have been obtained with FreeFem++. It is a free software developed at the Jacques-Louis Lions laboratory, in Paris. Its purpose is to solve partial dierential equations using the nite-element method. Roughly, this method allows to numerically solve an equation

div(A∇u) = q, u ∈ H (...a)
FreeFem++ is free in the sense that it can be obtained free of charge, but it also means it is open-source and can be freely shared, studied and modied. It is released under the lesser general public license.

Require: f Source density

Require: N Number of time iterations t ← U , V ← KP( f , )
Target is the uniform density dU , dV ← , This does not really matter

for k from to N -do p ← det(∇ V ) + t div( Co ∇ V * ∇dV ) dU ← S(∂ , dU = p dx ) No control over the result q ← det(∇ V ) -∂ , V -( -∂ , V )(∂ , p dx ) A ← M([[t ( -∂ , V ), t ∂ , V ], [t ∂ , V , -∂ , U -t ∂ , V ]]) dV ← S(div(A∇dV ) = q)
No control over the result dU ← dU - (If we work on the torus, there is a priori no boundary condition.) The set H is then replaced with a nite-dimensional subspace V ⊂ H , for if this subspace V is well chosen, then

dU dx + t dV dx -t dV dx dx dV ← dV - dV dx U ← U + dU /N V ← V + dV /N t ← t +/N end for return U + V
u V ∈ arg min ∈V A∇ |∇- q
should be a good approximation of the real solution. Then, if we denote by e ,...,e N an orthonormal basis of V , the problem is then equivalent to solve a system

              a , ••• a ,N . . . . . . . . . a N , ••• a N ,N                             u . . . u N               =               q . . . q N               , (...b)
Figure .: A × mesh on the torus. The space P on this mesh is of dimension N = .

with

a i ,j = A∇e i |∇e j , u k = ∇e k |∇u, q k = qe k , because u = u k e k and q = q k e * k .
Solving (...a) is therefore reduced to solving the (rather big) linear system (...b).

The space V used here is P , the set of continuous map u over T that are ane on each of the cells of a given mesh-as the one represented on gure ., on this page.

... We have tested our algorithm on a × mesh, with a time step h = /, with four initial densities:

. The rst one is a tensor product,

f (x , ) = + sin(πx ) + sin(π) .
On gure ., on page , it is possible to compare this density f and the density we get with our computation of Brenier's map, that is det(∇T B ). It is not dicult to check that the Knothe-Rosenblatt rearrangement is then theoretically optimal. Indeed, we see on gure . that Brenier's map is very close. The L error that is given is

ε := f -det(∇T ) L f L .
. The second initial density the algorithm was tested with is:

f (x , ) = - cos(πx ) + cos(π) .
Notice on gure ., on page that the computation of Brenier's map is symmetric, as it should, while Knothe's rearrangement is not. We can see an artifact the left, which is unaccounted for.

. The third initial density is

f (x , ) = + sin(πx ) sin(π) .
This case is interesting, because the projections on the rst axis are constant,

f (x , ) d ≡ ,
and as a consequence the Knothe-Rosenblatt rearrangement's rst component is zero (see gure ., on page ). As can be seen on gure ., there are more pronounced artifacts on the left and right boundaries, which are hard to explain since all the computations are made on the torus.

. For the last initial density, we have taken two Gaussian measures that have been made periodic. Artifacts are still present (see gure ., on page ).

All the FreeFem++ scripts can be found on my website:

hp://www.normalesup.org/~bonnoe/thesis/

Figure .:

The Knothe rearrangement (gray) is close to be optimal, but is not ; compare with the computation of Brenier's map (black), which is symmetric.

Chapter

An isotropic version of the IDT algorithm ... In image processing, it is often necessary to transfer the color palette of a reference picture to a target picture-for instance, to homogenize the aspect of a series of shots, e.g. in a lm. The two color palettes can be described by measures on the space of all the colors, and any transport map between them yields a possible transfer of coloring. In , François Pitié, Anil C. Kokaram, and Rozenn Dahyot [] proposed an algorithm to compute such a transfer, which they called "Iterative Distribution

Transfer" algorithm. It is based on a succession of unidimensional optimal matching between the projections of the distributions along dierent axes.

The idea was later taken up by Marc Bernot, who noticed the procedure could be somehow homogenized-indeed, the result of the initial algorithm seems to depend very much on the particular set of axes chosen at each iteration. His remedy was, at each step, to compute matchings for all the axes-instead of selecting a particular subset-, and then average the result. This new version, briey exposed in a paper he wrote with Julien Rabin, Gabriel Peyré, and Julie Delon [], can be seen as an explicit Euler scheme for the squared sliced Wasserstein distance. Alas, no proof exist for the general convergence of the algorithm toward the target measure, neither for the original nor the homogenized-i.e. isotropic-version.

In this chapter, I would like to present a continuous version of the isotropic algorithm, dened as a gradient ow for the squared sliced Wasserstein distance in the space of probability measures, in the sense of the theory developed by Luigi Ambrosio, Nicola Gigli and Giuseppe Savaré []. I was unable to get convergence toward the target measure, but this point of view might still provide a way to get it.

. The sliced Wasserstein distance ... Sliced Wasserstein distance. For any direction θ ∈ S d -, let us denote by θ * the orthogonal projection on Rθ , that is, θ * (x ) := θ |x. Given two probability measures µ and ν , the sliced Wasserstein distance between them is dened as

SW p (µ, ν ) := S d - W p (θ * # µ, θ * # ν ) p dθ /p .
At rst sight, the adjectif "sliced" does not seem to properly describe what the distance represents. It might be more appropriate to talk about a "projected Wasserstein distance" or "Radon-Wasserstein distance", as the projections θ * # µ and θ * # ν are sometimes called the Radon transforms of µ and ν . However, in Fourier mode, it does result in a slicing, since F (θ * # µ)(s) = Fµ (sθ ). This is quite convenient, as we can see in the proof of the next statement.

... P. The sliced Wasserstein distance is, indeed, a distance.

Proof. The triangular inequality is trivial; all there is to show is that SW p (µ, ν ) = implies µ = ν . But if SW p (µ, ν ) = , then θ * # µ = θ * # ν for almost every θ ∈ S d -, and this, in turn, yields

Fµ (sθ ) = R d e -i πsθ |x dµ (x ) = F (θ * # µ)(s) = F (θ * # ν )(s) = Fν (sθ ).
Since the Fourier transform is injective, we get µ = ν .

.

.. P. It µ, ν ∈P p (R d ), then SW p (µ, ν ) p ≤ c d ,p W p (µ, ν ) p , with c d ,p = d S d - |θ | p p dθ ≤ .
Notice c d ,p ≤ /d as soon as p ≥ .

Proof. Let γ ∈ Γ o (µ, ν ) be an optimal transport plan. Then (θ * ⊗ θ * ) # γ is a transport plan between θ * # µ and θ * # ν , so

W p (θ * # µ, θ * # ν ) p ≤ θ |x-θ | p dγ (x , )
Hence, as

θ |z p dθ = d |z| p |θ | p p dθ = c d ,p |z| p , SW p (θ * # µ, θ * # ν ) p ≤ θ |x-θ | p dθ dγ (x , ) ≤ c d ,p x - p dγ (x , ) ≤ c d ,p W p (µ, ν ) p .
... Lemma. There is a constant C d > such that, for all µ, ν supported in B(, R),

W (µ, ν ) ≤ C d R d/(d+) SW (µ, ν ) /(d+) .
Proof. First, let us recall proposition .. on page :

W (µ, ν ) = sup ψ d (µ -ν )         ψ ∈ Lip (R d ) .
Then, if we take φ ∈ C ∞ c (R d ) such that φ is radial, φ ≥ , supp φ ⊂ B(, ) and φ = , and set φ λ (x ) := φ(x/λ)/λ d , and µ λ := φ λ * µ, and ν λ := φ λ * ν , then, denoting also by f the Fourier transform of f ,

ψ d (µ λ -ν λ ) = ψ (ξ ) μ (ξ ) -ν (ξ ) φ(λξ ) dξ = S d - ∞ ψ (rθ ) μ (rθ ) -ν (rθ ) φ(λr )r d -dr dθ = S d - R ψ (rθ ) F (θ * # µ)(r ) -F(θ * # ν )(r ) φ(λr )r d -dr dθ , which implies ψ d (µ λ -ν λ ) = S d - R ψ (rθ )e i πru -ψ (rθ )e i πr φ(λr )r d -dr dγ θ (u, ) dθ , (...a)
where, for each θ , we have taken

γ θ ∈ Γ o (θ * # µ, θ * # ν ) optimal. However, R ψ (rθ )e i πru -ψ (rθ )e i πr φ(λr )r d -dr = ψ (x )e i πr (u -θ |x) -ψ (x ) i π ( -θ |x) φ(λr )r d -dx dr .
Dividing the integral in two parts, and replacing x with x + uθ in the rst part, and x with x + θ in the second part, we get R ψ (rθ )e i πruψ (rθ )e i πr φ(λr )r d -dr

= ψ (x + uθ ) -ψ (x + θ ) e -i πr θ |x φ(λr )r d -dx dr . Since γ θ is supported in [-R, R] , and µ λ , ν λ are supported in B(, R + λ), we can assume the map x → ψ (x + uθ ) -ψ (x + θ) is supported in B(, R + λ)
for almost every u, , and R ψ (rθ )e i πruψ (rθ )e i πr e -πλr r d -dr

≤ (R + λ) d |S d -| |u -| φ(λr )|r | d -dr ≤ (R + λ) d |S d -| λ d φ(r )|r | d -dr |u -| ≤ (R + λ) d C d λ d |u -|.
Thanks to (...a), this yields

W (µ λ , ν λ ) = sup ψ ψ d (µ λ -ν λ ) ≤ C d (R + λ) d λ d SW (µ, ν ), (...b)
although perhaps with a dierent constant C d .

Let us now nd an upper bound on

W (µ, ν ) -W (µ λ , ν λ ). Notice ψ d (µ -ν ) -W (µ λ , ν λ ) ≤ ψ d (µ -ν ) - ψ d (µ λ -ν λ ) ≤ (ψ -φ λ * ψ ) d (µ -ν ). But (ψ -φ λ * ψ ) d (µ -ν ) = ψ (x ) -ψ (x -) φ λ () d d (µ -ν )(x ) = ψ (x ) -ψ (x -λ ) φ() d d (µ -ν )(x ),
and for any ∈ B(, ),

ψ (x ) -ψ (x -λ ) d (µ -ν )(x ) ≤ ψ (x ) -ψ (x -λ ) d (µ + ν )(x ) ≤ λ||, thus ψ d (µ -ν ) -W (µ λ , ν λ ) ≤ λ ||φ() d.
Taking the supremum over ψ , we get

W (µ, ν ) -W (µ λ , ν λ ) ≤ C d λ.
Combining this last inequality with (...b), we obtain

W (µ, ν ) ≤ C d (R + λ) d λ d SW (µ, ν ) + λ .
If we take λ = R d/(d+) SW (µ, ν ) /(d+) , we get

W (µ, ν ) ≤ C d (R + λ) d R d + R d/(d+) SW (µ, ν ) /(d+) .
As SW (µ, ν ) ≤ R, we have λ ≤ /(d+) R, hence the announced inequality, with maybe yet another constant C d .

... T (Equivalence of SW p and W p ). There is a constant C d ,p > such that, for all µ, ν ∈P(B(, R)), d+) .

SW p (µ, ν ) p ≤ c d ,p W p (µ, ν ) p ≤ C d ,p R p -/(d+) SW p (µ, ν ) /(
Proof. This follows from the previous lemma, as on the one hand,

W p (µ, ν ) p ≤ (R) p -W (µ, ν ),
and on the other hand

SW (µ, ν ) ≤ SW p (µ, ν ).
Notice the exponent p -/(d +) on R is the only one for which the inequality would be preserved by dilations, given the exponent on SW p .

... P. Let µ, ν ∈P(K ), with K a compact subset of R d , and assume ν absolutely continuous. Then, for each direction θ ∈ S d -, there is a Kantorovich potential

ψ θ between θ * # µ and θ * # ν for the cost c θ (s, t ) = |s -t | /, and, if μ ∈P(K ), lim ε→ + SW (( -ε )µ + ε μ, ν ) -SW (µ, ν ) ε = S d - K ψ θ (θ |x) d( μ -µ)(x ) dθ .
This is to be compared to proposition .. on page , which dealt with a similar result for the usual Wasserstein distance.

Proof. Since ν is absolutely continuous, for each θ the projected measure θ * # ν is also absolutely continuous on θ * (K ); therefore, there is indeed a Kantorovich potential ψ θ between θ * # µ and θ * # ν . Since ψ θ is, a priori, not optimal between (ε )µ + ε μ and ν ,

lim inf ε→ + SW (( -ε)µ + ε μ, ν ) -SW (µ, ν ) ε ≥ ψ θ (θ |x) d( μ -µ)(x ) dθ . Conversely, let ψ ε θ be a Kantorovich potential between θ * # ( -ε)µ + ε μ and θ * # ν, with ψ ε θ dθ * # [( -ε)µ + ε μ] = . Then, SW (( -ε)µ + ε μ, ν ) - SW (µ, ν ) ≥ ε ψ ε θ (θ |x) d( μ -µ)(x ) dθ .
As in the proof of proposition .. on page , ψ ε θ uniformly converges, when ε → to a Kantorovich potential for the pair (θ * # µ, θ * # ν ). Then, by Lebesgue's dominated convergence theorem,

lim sup ε→ + SW (( -ε )µ + ε μ, ν ) -SW (µ, ν ) ε ≤ ψ θ (θ |x) d( μ -µ)(x ) dθ .
... P. Let µ and ν ∈P(K ), with K a compact subset of R d , and assume µ is absolutely continuous. For any θ ∈ S d -, let ψ θ is the (unique up to an additive constant) Kantorovich potential between θ * # µ and θ * # ν .I fζ is a dieomorphism of K, then

lim ε→ SW ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε = ψ θ (θ |x) θ |ζ (x ) dθ dµ (x ).
This is the sliced equivalent of proposition .. on page .

Proof. As ψ θ is a Kantorovich potential between θ * # µ and

θ * # ν , SW ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≥ ψ θ (θ |x + εζ (x )) -ψ (θ |x) ε dθ dµ (x ).
Since ψ is dierentiable almost everywhere, Lebesgue's dominated convergence theorem ensures

lim inf ε→ + SW ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≥ ψ θ (θ |x) θ |ζ (x ) dθ dµ (x ).
Conversely, let γ θ ∈ Γ o (θ * # µ, θ * # ν ) be an optimal plan. Then, we can extend

γ θ into π θ ∈ Γ(µ, ν ) such that (θ * ⊗ θ * ) # π θ = γ θ ; for instance, by disintegrating µ ⊗ ν with respect to θ * ⊗ θ * , ξ (x , ) d(µ ⊗ ν )(x , ) = ξ (uθ + x , θ + ) d[µ ⊗ ν ] u , ( x , ) d[(θ * ⊗ θ * ) # (µ ⊗ ν )](u, ),
and then replacing

(θ * ⊗ θ * ) # (µ ⊗ ν ) with γ θ : ξ (x , ) dπ θ (x , ) = ξ (uθ + x , θ + ) d[µ ⊗ ν ] u , ( x , ) dγ θ (u, ). Now, [(θ * + εθ * (ζ )) ⊗ θ * ] # π θ is a transport plan between θ * # [Id +εζ ] # µ and θ * # ν; hence, SW ([Id +εζ ] # µ, ν ) -SW (µ, ν ) ≤ θ |x + εζ (x ) - - θ |x - dπ θ (x , ) dθ .
But for π θ -almost every pair (x , ), we have

θ | = θ |x-ψ θ (θ |x), so SW ([Id +εζ ] # µ, ν ) -SW (µ, ν ) ≤ ψ θ (θ |x) -εθ |ζ (x ) - ψ θ (θ |x) dπ θ (x , ) dθ .
This immediately yields

lim sup ε→ + SW ([Id +εζ ] # µ, ν ) -W (µ, ν ) ε ≤ ψ θ (θ |x) θ |ζ (x ) dθ dµ (x ).
. The Iterative Distribution Transfer algorithm ... The algorithm proposed by François Pitié, Anil C. Kokaram, and Rozenn Dahyot [] starts from a given measure µ, and, for any target measure ν , builds a sequence (µ n ) n ∈N such that µ = µ and µ n seems to tend to ν when n tends to innity.

Convergence, however, is assured only empirically, as the authors were able to prove it only when ν is a Gaussian measure.

If µ n has been set, then µ n+ is dened as follows. First, chose an orthogonal basis B n = (e n ,...,e n d ) in R d , and take the projections e n i * # µ n and e n i * # ν . For each axis i, there is an unidimensional optimal matching between the projections, which we will denote by t e n i : R → R. Let . Alternatively, if the bases B n are dense, then µ n → ν .

It may be said that the original proof by François Pitié, Anil C. Kokaram, and Rozenn Dahyot lacks in precision, on two counts:

• The absolute continuity of the measures µ n is crucial, but not proved.

• The reader might be misled into believing some kind of uniform continuity for (θ , µ) → Ent(θ # µ |θ # ν ) is used, which, of course, is not possible. The following proof addresses both issues.

Proof. The rst thing to check is that the measures µ n are always absolutely continuous. If we know µ n is absolutely continuous, then the transport map T n , which is such that µ n+ = T n# µ n , is W , . Moreover, it is easy to check from its denition that T n is injective on the support of µ n . Then, there is a µ n -negligible set N n and a sequence

(A k ) k ∈N of disjoint Borel sets such that R d = N n ∪ k ∈N A k and T n A k = a k with a k ∈ C
µ n+ (N ) ≤ k ∈N ε k A k 1 N (a k (x ))ρ n (x )|det(Da k )| dx = .
Therefore, µ n+ is also absolutely continuous.

Now, the key property of ν is that, being a Gaussian measure, it enjoys a tensorization property: for any basis B = (e ,...,e d ), we always have

ν = e * # ν ⊗•••⊗e * d # ν.
Therefore, if (x i ) are the coordinates of x in the base B and if we denote by f n , f n ,i , and , i the respective densities of µ n , e * i # µ n , and ν , e * i # ν, we get

Ent (µ n    ν ) = f n ln f n f n , •••f n ,d + f n ln f n , •••f n ,k ••• k = Ent µ n      e * # µ N ⊗•••⊗e * d # µ n + d i= Ent e * i # µ n      e * i # ν .
If B is now the basis chosen to build µ n+ , i.e. B = B n = (e n ,...,e n d ), we have

Ent e n i * # µ n+      e n i * # ν = .
On the other hand,

Ent µ n+      e n * # µ n+ ⊗•••⊗e n d * # µ n+ = ln f n+ () f n+ ,i ( i ) dµ n+ () = ln       f n+ (T (x )) f n+ ,i (t e n i (x i ))       dµ n (x ),
and as DT is diagonal, with t e n ,...,t e n d on the diagonal, and

f n ,i = ( f n+,i • t e i n )t e i n ,
we get

f n+ (T (x )) = f n (x ) det DT (x ) = f n (x ) t e n (x ) ...t e n d (x d ) = f n (x ) d k= f n+ ,i (t e n i (x i )) f n ,i (x i )
.

This implies Ent(µ

n+ |e n * # µ n+ ⊗•••⊗e n d * # µ n+ ) = Ent(µ n |e n * # µ n ⊗•••⊗e n d * # µ n ). Hence, Ent (µ n+    ν ) = Ent µ n+      e n * # µ n+ ⊗•••⊗e n d * # µ n+ + d i= Ent e n i * # µ n+      e n i * # ν = Ent µ n      e n * # µ n ⊗•••⊗e n d * # µ n = Ent (µ n    ν ) - d i= Ent e n i * # µ n      e n i * # ν .
As the entropy is nonnegative, Ent(µ n |ν ) is nonincreasing, and so converges. But, according to Michel Talagrand's inequality [],

W (e

n i * # µ n , e n i * # ν ) ≤ C Ent e n i * # µ n      e n i * # ν .
Thus,

d i= W (e n i * # µ n , e n i * # ν ) ≤ C (Ent (µ n    ν ) -Ent (µ n+    ν )) -→ n→∞ .
Then:

. If B n = (e n ,...,e n d ) is independent from µ n , with a uniform law on O(d ), then

E W (e n k * # µ n , e n k * # ν ) = E W (e n k * # µ n , e n k * # ν )      µ n = SW (µ n , ν ) ,
and thus, by Lebesgue's dominated convergence theorem, E[SW (µ n , ν ) ] → .

. The sequence

(µ n ) n ≥ is tight, because for any n ≥ , || dµ n () = d k= t e n - k (e n - k |x) dµ n -(x ) = || dν ().
Let µ be a limit point. If all the bases (B n ) form a dense subset of all orthogonal bases of R d , then for any θ ∈ S d -we can nd an extraction n k →∞such that e n k → θ , and µ n k → µ still. Let ε > , then for n k big enough,

W e n k * # µ n k , e n k * # ν < ε and W (µ n k , µ) < ε ,
and since e n can be as close to θ as we may desire, we can also impose

W e n k * # ν , θ * # ν < ε and W e n k * # µ, θ * # µ < ε as well. Because W e n k * # µ n k , e n k * # µ < W (µ n k , µ), we get W (θ # µ, θ # ν ) < ε.
Letting ε → , we obtain SW (µ, ν ) = .

... If we work only with discrete measures that are sums of N Dirac masses, as

µ = N N k= δ x k , with x k ∈ R d ,
then, setting x := (x ,...,x N ), we get a vector of (R d ) N . Letting δ ,...,δ N be the canonical basis of R N , we can write

x = N k= x k ⊗ δ k .
We will write the correspondence between µ and x as µ ∼ x.

... Lemma. The solution to the Monge-Kantorovich problem between two discrete measures µ ∼ x and ν ∼ y is given by a transport map T , such that

T (x k ) = σ T (k ) .
for an optimal permutation σ T ∈ S N , such that

W (µ, ν ) = N k= x k -σ T (k ) = min σ ∈S N N k= x k -σ (k ) .
Proof. This follows immediately from Choquet's and Birkho's theorems (see Cédric Villani's book [, p. ]).

We will conveniently set y σ = ( σ () ,..., σ ( N ) ) for any σ ∈ S N , so that, in particular, W (µ, ν ) = |xy σ T | /. Notice ν ∼ y σ as well.

... If µ is the sum of N Dirac masses, then, for any θ ∈ S d -, the projected measure θ * # µ is also a sum of Dirac masses:

θ * # µ = N N k= δ θ |x k ,
and, with our notation, we can write

θ * # µ ∼ N k= θ |x k δ k = N k= (θ * ⊗ I N )(x k ⊗ δ k ) = (θ * ⊗ I N )x.
The algorithm builds a sequence µ n ∼ x n , from an initial point µ ∼ x and a reference target measure ν ∼ y, by setting µ n+ := T n# µ n with

T n := d i= (t e n i • e n i * )e n i ,
where t e n i is the optimal map between e n

W (θ * # µ, θ * # ν ) = (θ * ⊗ I N )(x -y σ θ ) .
Proof. Let σ ∈ S N . Then,

y σ = N k= k ⊗ δ σ -(k ) = N k= k ⊗ P - σ δ k = N k= (I d ⊗P - σ )( k ⊗ δ k ) = (I d ⊗P - σ )y.
As the optimal map t θ between θ * # µ and θ * # ν is given by a permutation

σ θ ∈ S N , such that θ |x k is sent to t θ (θ |x k ) = θ | σ θ (k ) , we have W (θ * # µ, θ * # ν ) = N k= θ |x k -σ θ (k ) = (θ * ⊗ I N )(x -y σ θ ) .
... P. We set, for all x ∈ (R d ) N and σ ∈ S d N and any basis e,

F e (x, σ ) = d i= (e * i ⊗ I N )(x -y σ i ) .
Then, if e n is the basis which allows us to dene µ n+ from µ n , we have

F e n (x n , σ e n ) = min σ ∈S d N F e n (x n , σ ) = d i= W (e n i * # µ n , e n i * # ν ) .
If σ e n represent the sequence of optimal permutations, then

x n+ = x n -∇ x F e n (x n , σ e n ) and x n+ -x n = F e n (x n , σ e n ).
Thus, the algorithm can be seen as a kind of steepest-descent method. If it were not to depend on an ever-changing basis e n , it would be (close to) an explicit Euler scheme for a gradient ow.

Proof. On the one hand, x n+ is dened by

x n+ k := T (x n k ) = d i= t e n i (e n i |x n k ) e n i = d i= e n i | σ e n i (k ) e n i = d i= e n i e n i * σ e n i (k ) ,
where σ e n i is the optimal permutation associated to t e n i . Thus, On the other hand,

∇ x F e (x, σ ) = d i= (e i ⊗ I N ) * (e * i ⊗ I N ) x -y σ i = d i= (e i e * i ⊗ I N ) x -y σ i =        x - d i= (e i e * i ⊗ I N )(I d ⊗P - σ i )y        =        x - d i= (e i e * i ⊗ P - σ i )y        . Thus, ∇ x F e n (x n , σ e n ) = (x n -x n+ ). Moreover, x n -x n+ = d i= (e i e * i ⊗ I N ) x n -y σ e n i = d i= e * i ⊗ I N x n -y σ e n i = F e n (x n , σ e n ).
. Marc Bernot's isotropic definition Then, if µ ∼ x and ν ∼ y,

min σ F (x, σ ) = SW (µ, ν ) .
We can introduce a parameter h > , and dene a sequence (x n ) by

x n+ := x n -h∇ x F (x n , σ n ), (...a)
where σ n θ is the optimal permutation between θ * # µ n and θ * # ν , such that SW (µ, ν ) = F (x n , σ n ).

... Lemma. We have, for any h ∈ (R d ) N ,

F (x n + h, σ n ) = F (x n , σ n ) + S d - (θθ * ⊗ I N )(x n -y σ θ ) h dθ + d |h| .
Therefore

x n+ = - h d x n + h S d - (θθ * ⊗ P - σ n θ )y,
and

SW (µ n , ν ) is nonincreasing if h < d.
Proof. The expression for x n+ comes from θθ * dθ = I d /d, and

∇ x F (x n , σ n ) = (θθ * ⊗ I N ) x n -y σ n θ dθ = d x n - (θθ * ⊗ I N )(I d ⊗P - σ θ )y dθ = d x n - (θθ * ⊗ P - σ θ )y dθ .
As for the nonincreasingness of SW (µ n , ν ),

SW (µ n+ , ν ) = min σ F (x n+ , σ ) ≤F (x n -h∇ x F (x n , σ n ), σ n ) ≤F (x n , σ n ) -h ∇ x F (x n , σ n ) + h d ∇ x F (x n , σ n ) .
. Implicit version ... Equation (...a) denes an explicit Euler scheme for the sliced Wasserstein distance. On R d , given a smooth functional F : R d → R, the explicit Euler scheme yields a sequence (x n ) n ∈N , given a starting point x and a time step h > , by setting

x n+ := x n -h∇F (x n ).
The implicit Euler scheme, on the other hand,

x n+ := x n -h∇F (x n+ ),
can be obtained by, at each step, taking

x n+ ∈ arg min

x h |x -x n | + F (x ) .
In our case, we can dene a sequence µ n ∼ x n using such an implicit scheme, by taking

x n+ ∈ arg min

x n h x -x n + min σ F (x, σ ) .
This corresponds to ours setting

µ n+ ∈ arg min µ h W (µ, µ n ) + SW (µ, ν ) . (...a)
... One of the diculties of working discrete measures, is that the (sliced) Wasserstein distance is given by an optimal map-or many, for the sliced distance-, but a bijection on a discrete space can only be a permutation. It is hard to nd any smoothness of the optimal map with respect to the measures under such circumstances.

Things are simpler when the measures are absolutely continuous, as there is some regularity (see the article by Grégoire Loeper []). Furthermore, (...a) does not lose any meaning if we drop the assumption the measures are all discrete-that is even the starting point of the theory of gradient ows in the space of probability measures, as developed by Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré [].

In the rest of this section, we will therefore show that, given two absolutely continuous measures µ and ν , we can dene a sequence (µ n ) n ∈N with

µ n+ ∈ arg min µ h W (µ, µ n ) + F (µ) ,
where h > is a time step and

F (µ) := SW (µ, ν ) .
We will work on the closed unit ball B = B(, ), and assume ν has a strictly positive, smooth density on B. As the algorithm may force µ n to venture out of B, we will allow it to be dened on rB, with r > √ d.

... Lemma. Let us x a time step h > , and a radius r > √ d. For a probability measure µ on rB = B(, r ) that is absolutely continuous with a strictly positive, smooth density ρ , there is a probability measure µ on rB minimizing

G(µ) := F (µ) + h W (µ, µ ) + δH (µ), with H (µ) :=          rB ρ (x ) ln ρ (x ) dx if dµ (x ) = ρ (x ) dx , +∞ otherwise.
Moreover, this optimal µ has a Lipschitz density ρ, which is strictly positive on rB and such that

ρ L ∞ ≤ +h/ √ d d ρ L ∞ .
Proof. We follow methods developed by Guillaume We denote by ψ θ the Kantorovich potential between θ * # µ and θ * # ν , and φ the Kantorovich potential between µ and µ .

Let μ be another probability measure on rB, absolutely continuous with a density ρ. Then, proposition .. on page and proposition .. on page together yield

lim sup ε→ + H (µ) -H (( -ε)µ + ε μ) ε ≤ δ rB Ψ(x )( ρ (x ) -ρ (x )) dx where Ψ(x ) := S d - ψ θ (θ |x) dθ + h φ(x ). Since t → t ln t is convex, setting ρ ε = ( -ε )ρ + ε ρ, we can write ρ ln ρ -ρ ε ln ρ ε ≥ ε ( + ln ρ ε )(ρ -ρ).
If ρ (x ) ≥ ρ (x ), then ρ ε (x ) ≥ ρ (x ), and thus

ρ ln ρ -ρ ε ln ρ ε ≥ ε ( + ln ρ)(ρ -ρ).
Where ρ (x ) ≤ ρ (x ), this last inequality still holds, because then ln ρ ε (x ) < ln ρ (x ), and ρ (x ) -ρ (x ) < .

In particular, if we take μ uniform on rB, i.e. ρ (x ) = /(r d |B|), then,

ρ ln ρ -ρ ε ln ρ ε ≥ ε | + ln ρ|(ρ + ρ) when ρ > , ρ ln ρ -ρ ε ln ρ ε ≥-( + ln( ερ))ε ρ when ρ = .
Integrating, since ρ is constant we get

H (µ) -H (( -ε)µ + ε μ) ε ≥-| + ln ρ|-( + ln(ε ρ)) |{ρ = }| r d |B| .
As we have an upper bound when ε → , necessarily |{ρ = }| = , i.e. ρ > almost everywhere.

Now, let ρ = ηρ with η ∈ L ∞ . Then,

ln(ρ + ε ( ρ -ρ)) = ln((+ε (η -))) + ln(ρ).
Therefore, thanks to Lebesgue's dominated convergence theorem,

rB ( + ln ρ)(ρ -ρ) = lim ε→ ( + ln ρ ε )(ρ -ρ) ≤ lim sup ε→ H (µ) -H (( -ε )µ + ε μ) ε ≤ δ Ψ( ρ -ρ),
and this yields

Ψ(x ) + δ ln ρ (x ) ρ (x ) dx ≥ Ψ(x ) + δ ln ρ (x ) ρ (x ) dx .
We set m = ess inf {Ψ + δ ln ρ}. For any m > m, by denition, A := {m > Ψ + δ ln ρ} has a nonzero measure, so we can take η = λ1 A with λ such that ηρ is still a probability measure. Then, the previous inequality gives

m ≥ Ψ + δ ln ρ ηρ ≥ Ψ + δ ln ρ ρ ≥ m.
Letting m converge toward m, we get Ψ + δ ln ρ is constant, and equal to m almost everywhere. This implies

ρ = exp((m -Ψ)/δ ).
As Ψ is Lipschitz, so is ρ. It then follows from theorem .. on page that the potential φ between µ and µ is C , and I d -D φ > andψ θ > . Let us denote by f θ and θ the densities of θ * # µ and θ * # ν , and F θ and G θ their cumulative distributions. If m f and m stand for the minima of f and , and M f and M for their maxima, then

m f √ -t ≤ f θ (t ) ≤ M f √ -t , m √ -s ≤ θ (s) ≤ M √ -s .
Let F θ and G θ be the cumulative distributions of f θ and θ . If we dene

U ε := x ∈ rB      ∀ θ ∈ S d -, F θ (θ |x) ∈ (ε , -ε) , V ε := ∈ B      ∀ θ ∈ S d -, G θ (θ |) ∈ (ε , -ε) ,
then f θ and θ are uniformly bounded and bounded above on θ * (U ε ) and θ * (V ε )

respectively. Moreover, it follows from the denition of the optimal map, t θ := G - θ •F θ , that t θ (θ |x) ∈ θ * (V ε ) for any x ∈ U ε . Then, thanks to theorem .. on page again, we get that andC ,α up to the boundary. Moreover,

ψ θ • θ * is C on U ε , and -ψ θ > . Since t θ = Id -ψ θ = G - θ • F θ ,we also have ψ θ • θ * is C ,α on rB, up to the boundary. By a consequence of Lebesgue's dominated convergence theorem, Ψ = φ/h ψ θ • θ * dθ is C on U ε ,
∇Ψ(x ) = ∇φ h + ψ θ (θ |x)θ dθ , ∇ Ψ(x ) = ∇ φ h + ψ θ (θ |x)θ ⊗ θ dθ .
Therefore, ρ = exp((m -Ψ)/δ ) is C in the interior, C ,α up to the boundary, and

∇ρ = -ρ ∇Ψ δ and ∇ ρ = ρ ∇Ψ ⊗∇Ψ δ -ρ ∇ Ψ δ .
If ρ is maximum in x on the boundary, i.e. for |x | = r , then, as t → ρ (tx ) is maximal for t = , we must have ∇ρ (x )|x ≥. Thus,

∇Ψ(x )|x ≤ (...a)
But, the transport map Id -∇φ between µ and µ takes its values in supp µ = rB, so

r ≥| x -∇φ(x )| ≥| x | + |∇φ(x )| -∇φ(x )|x ≥ r -∇φ(x )|x .
Hence, ∇φ(x )|x ≥. Likewise, for any direction θ , the map

t θ = Id -ψ θ takes its values in θ * (B) = [-, ], so ψ θ (θ |x )θ dθ x = ψ θ (θ |x )θ |x dθ ≥ |θ |x | -| θ |x -ψ θ (θ |x )| dθ ≥ |θ |x | dθ - ≥ r d - .
As we have assumed r > √ d, we nally get ∇Ψ(x )|x > , and this contradicts (...a). Thus, ρ is maximum in a point x in the interior. Since ∇ρ (x ) = and

∇ ρ (x ) ≤ , we must have ∇ Ψ(x ) ≥ . Hence, as ψ θ < , ∇ φ(x ) ≥-h ψ θ (θ |x )θ ⊗ θ dθ ≥-h θ ⊗ θ dθ ≥- h √ d I d .
This, in turn, yields:

ρ ∞ = ρ (x ) = ρ (x -∇φ(x )) det I d -∇ φ(x ) ≤ + h √ d d ρ ∞ ,
... P. For any time step h > , and any probability measure µ ∈ P (rB) that is absolutely continuous with a density ρ ∈ L ∞ , there is µ ∈P (rB)

minimizing

F (µ) + h W (µ, µ ) ,
which is absolutely continuous, with a density ρ ∈ L ∞ such that

ρ L ∞ ≤ +h/ √ d d ρ L ∞ .
Proof. Let us rst assume ρ ∈ C ∞ (rB). Then, according to lemma .. on page , for any δ > , there is µ δ minimizing

µ → F (µ) + h W (µ, µ ) + δH (µ),
with a Lipschitz density ρ δ such that

ρ δ L ∞ ≤ +h/ √ d d ρ L ∞ .
Up to an extraction, we can assume µ δ converges toward µ in P (rB) and ρ δ converges toward ρ for the weak-star topology of L ∞ , with ρ the density of µ. Then, ρ L ∞ ≤ (+h/ √ d ) d ρ L ∞ , and this implies

H (µ) ≤ + +h/ √ d d ρ L ∞ ln + +h/ √ d d ρ L ∞ < ∞,
because t → t ln t is increasing on (/e , ∞) and positive on (, ∞).

Let μ be such that F ( μ) +W ( μ, µ ) /(h) is minimal, and let e t be the heat kernel, e t (x ) = exp(-π |x | /t )/ √ t. We set μt = e t * μ. Then, μt → μ in P (rB), and if

H ( μ) = ∞, then H ( μt ) →∞as well. Let t δ be such that H ( μt δ ) < / √ δ ; then, F (µ) + h W (µ, µ ) ≤ lim inf δ → F (µ δ ) + h W (µ δ , µ ) + δH (µ δ ) ≤ lim inf δ → F ( μt δ ) + h W ( μt δ , µ ) + δH ( μt δ ) ≤ F ( μ) + h W ( μ, µ ) .
Thus, µ is a minimizer as well.

We now drop the assumption ρ ∈ C ∞ . Then, for any t > , there is a minimizer

µ t ∈P (rB) for µ → F (µ) +W (µ, µ t ) /(h), which has a density ρ t ∈ L ∞ with ρ t L ∞ ≤ (+h/ √ d ) d ρ L ∞ .
Up to an extraction, µ t converges toward µ in P (rB) and ρ t converges toward ρ for the weak-star topology of L ∞ . This implies

ρ L ∞ ≤ +h/ √ d d ρ L ∞ .
And if μ is a minimizer for µ → F (µ) +W (µ, µ ) /(h), then

F (µ) + h W (µ, µ ) ≤ lim inf δ → F (µ t ) + h W (µ t , e t * µ ) + δH (µ t ) ≤ lim inf δ → F ( μ) + h W ( μ, e t * µ ) + δH ( μ) ≤ F ( μ) + h W ( μ, µ ) .
So µ is a minimizer as well.

. Continous version ... Generalized minimizing movements. Given a metric space X, a functional

F : [, ∞) × N × X × X → [-∞, ∞]
, and an initial point x ∈ X, a minimizing movement () relative to F and starting from x is a curve x : [, ∞) → X that is pointwise limit of a family x h : [, ∞) → X indexed by h > such that: Indeed, a gradient ow ẋ = -∇F (x ) in R d is the limit of the Euler implicit scheme:

• x h () = x for every h > ; • x h is constant on each interval [nh, (n +)h), so x (t ) = x (nh) for n = t/h; • x h (t + h) minimizes → F (h, n, , x (t )), if n = t/h. When x is limit of only a sequence x h k , with h k → ,
if x h (t + h) = x h (t ) -h∇F (x (t )), with x h constant on each interval [nh, (n +)h), then x h (t ) → x (t ); and x h (t + h) is just obtained from x h (t ) as a minimizer of → F (h, n, , x h (t )) with F (h, n, , x ) = h | -x | + F ().
Thus, a gradient ow in R d is a minimizing movement. But, unlike dierentiation, minimization can be performed in quite a general framework, as in a metric space.

There it is enough to replace the Euclidean distance with the metric distance in the previous expression of F .

... T. Let ν be a probability measure on B = B(, ), with a strictly positive, smooth density. Given an absolutely continuous measure µ ∈P(rB), with a density ρ ∈ L p , there is a Lipschitz generalized minimizing movement (µ t ) t ≥ in P (rB) starting from µ for the functional

F (h, n, µ + , µ -) := h W (µ + , µ -) + F (µ + ), with F (µ + ) = SW (µ + , ν ) .
Moreover, for each time t ≥ , the measure µ t has a density ρ t ∈ L p , and

ρ t L p ≤ e t √ d /q ρ L p .
Proof. For any time step h > , we use proposition .. on page to build a curve (µ h t ) t ≥ of absolutely continuous measures by induction, such that: For an arbitrary T > , we dene a measure µ h on [, T ] × rB with

• µ h = µ ; • µ h t is constant on [nh, (n +)h); • µ h t+h minimizes µ → F (µ) +W (µ, µ h t ) /(
∀ ξ ∈ C , [ ,T ] × rB ξ (t , x ) dµ h (t , x ) = [,T ] rB ξ (t , x ) dµ h t (x ) dt;
and it has a density ρ h ∈ L p ([, T ] × rB), dened by ρ h (t , x ) = ρ h t (x ). Then, there is h n → such that µ h n → µ in P (rB); moreover, the limit µ has necessarily a density ρ, and ρ h weakly converges to ρ in L r for any nite r ∈ [, p], with a weak-star convergence in L ∞ when p is innite. Let ρ t (x ) := ρ (t , x ). We want to show µ h t converges P (rB), and ρ h t weakly converges to ρ t in L r for all t ∈ [, T ] and for any nite r ∈ [, p] (even though we might have to redene µ t and ρ t on a negligible set of times t). First, there is a measure µ t whose density is ρ t , at least for almost any t, since

= δ t+δ t -δ ρ h t (x ) dx dt -→ h→ t+δ t -δ ρ t (x ) dx dt ,
and this implies ρ t is indeed a probability density. Next, we show µ h t must converge to µ

t . If ξ ∈ C (rB), ξ dµ h n t - ξ dµ h m t ≤ ξ dµ h n t - δ t+δ t -δ ξ dµ h n s ds + ξ dµ h m t - δ t+δ t -δ ξ dµ h m s ds + δ t+δ t -δ ξ dµ h n s ds - δ t+δ t -δ ξ dµ h m s ds . (...b) But, by taking γ ∈ Γ o (µ h t , µ h s ), we can rst obtain ξ dµ h t - ξ dµ h s ≤ ξ (x ) -ξ () dγ (x , ) ≤ ∇ ξ ∞ W (µ h t , µ h s );
then, as µ h t = µ h hn t for n t = t/h, and

F (µ h h(n+) ) + h W (µ h(n+) , µ hn ) ≤ F (µ h hn )
for every n, we get

W (µ h t , µ h s ) = W (µ h hn t , µ h hn s ) ≤ W µ h h(k+) , µ h hk ≤| n t -n s | W µ h h(k+) , µ h hk ≤ h|n t -n s | F (µ h t ) -F (µ h s ) ≤ Ch|n t -n s |W (µ h t , µ h s ) ≤ C (|t -s | + h) W (µ h t , µ h s ), which implies W (µ h t , µ h s ) ≤ C (|t -s | + h) . (...c) Thus, ξ dµ h t - δ t+δ t -δ ξ dµ h s ds ≤ δ t+δ t -δ ξ dµ h t - ξ dµ h s ds ≤ C ∇ξ ∞ δ t+δ t -δ (|t -s | + h) ds ≤ C ∇ξ ∞ (δ + h) . Because µ h n converge to µ, δ t+δ t -δ ξ dµ h n s ds -→ δ t+δ t -δ ξ dµ s ds;
therefore, (...b) shows ξ dµ h n t is Cauchy. But for almost all t ∈ [, T ], the limit can only be ξ dµ t . Thus, µ h n t converges to µ t , and this, with (...a), implies the densities ρ h n t weakly converge to ρ t in all L r for all nite r ∈ [, p], with

ρ t L p ≤ e t √ d /q ρ L p .
Moreover, (...c) yields

W (µ s , µ t ) ≤ lim inf n→∞ W (µ h n s , µ h n t ) ≤ C |t -s |.
. Continuity equation

∂ρ t ∂t + div( t ρ t ) = with t (x ) := - S d - ψ t ,θ (θ |x)θ dθ . More precisely, for any ξ ∈ C ∞ c ([, ∞) × B(, r )), ∞ B( ,r ) ∂ξ ∂t (t , x ) - S d - ψ t ,θ (θ |x)θ |∇ξ (t , x ) dθ ρ t (x ) dx dt = - B(,r ) ξ (, x )ρ (x ) dx .
The vector eld t is a tangent vector for the Riemannian structure of P (R d );

see the book by Luigi Ambrosio, Nicolas Gigli and Giuseppe Savaré [, chapter ] for denitions. Indeed, since ψ t ,θ is Lipschitz, if we set

Ψ t (x ) := S d - ψ t ,θ (θ |x) dθ ,
then Ψ t is also Lipschitz, and t = -∇Ψ t .

Proof. We will proceed in four steps.

. On the one hand, since µ h n → µ for some sequence

h n → , ∞ B(,r ) ∂ξ ∂t (t , x )ρ h n t (x ) dx dt -→ ∞ B(,r ) ∂ξ ∂t (t , x )ρ t (x ) dx dt .
On the other hand,

∞ B( ,r ) ∂ξ ∂t (t , x )ρ h n t (x ) dx dt = ∞ k= (k+)h n kh n B(,r ) ∂ξ ∂t (t , x )ρ h n t (x ) dx dt = ∞ k= B(,r ) [ξ ((k +)h n , x ) -ξ (kh n , x )] ρ h n kh n (x ) dx dt , because ρ h is constant on each interval [kh, (k +)h). Then, ∞ B( ,r ) ∂ξ ∂t (t , x )ρ h n t (x ) dx dt = - ξ (, x )ρ h n (x ) dx - ∞ k= ξ (kh n , x ) ρ h n kh n (x ) -ρ h n (k -)h n (x ) dx dt ,
and this means, if we set

ξ n k (x ) := ξ (kh n , x ), ξ (, x )ρ (x ) dx + ∞ ∂ξ ∂t (t , x )ρ t (x ) dx dt ∼ n→∞ -h n ∞ k= ξ n k (x ) ρ h n kh n (x ) -ρ h n (k -)h n (x ) h n dx dt . (...a)
. For any θ ∈ S d -, we can nd

γ θ ,h ,t ∈ Γ(θ * # µ h t , θ * # µ t , θ * # ν )
such that, if u, ū, stand for the variables and U, Ū, V for the corresponding projectors, then (U, V) # γ θ ,h ,t and ( Ū, V) # γ θ ,h ,t and (U, Ū) # γ θ ,h ,t are all optimal; indeed, if F , G, H stand for the cumulative distributions of the three measures, then we can just take

γ θ ,h ,t := (F -, G -, H -) # L .
Then, γ θ ,h ,t can then be extended into a measure π θ ,h ,t ∈ Γ(µ h t , µ t , ν ): rst, take a measure π ∈ Γ(µ h t , µ t ) optimal between µ h t and µ t ; next, disintegrate π ⊗ ν with respect to (θ * , θ * , θ * ) into a family

[ π ⊗ ν] u , ū , , such that, for any η, η(x , x , ) d[ π ⊗ ν ](x , x , ) = R (R d -) η(uθ + x , ūθ + x , θ + ) d[ π ⊗ ν] u , ū , ( x , x , ) d[(θ * , θ * , θ * ) # ( π ⊗ ν )](u, ū, ); then dene π θ ,h ,t by replacing (θ * , θ * , θ * ) # ( π ⊗ ν ) with γ θ ,h ,t in the previous expres- sion: η(x , x , ) dπ θ ,h ,t (x , x , ) = R (R d -) η(uθ + x , ūθ + x , θ + ) d[ π ⊗ ν ] u , ū , ( x , x , ) dγ θ ,h ,t (u, ū, ).
Now, let ψ h t ,θ be the Kantorovich potential between θ * # µ h t and θ * # ν , and, taking back the same ξ as in the rst point, set

I h ,t := B(,r ) S d - ψ h t ,θ (θ |x) θ |∇ξ (t , x ) dθ dµ h t (x ), I t := B(,r ) S d - ψ t ,θ (θ | x) θ |∇ξ (t , x ) dθ dµ t ( x );
we can write

I h ,t = θ |x -θ |∇ξ (t , x ) dπ θ ,h ,t (x ) dθ , I t = θ | x -θ |∇ξ (t , x ) dπ θ ,h n ,t (x ) dθ .
We conveniently dene Φ θ ,h ,t , (x ) := θ |xθ |∇ξ (t , x ); then,

I h ,t -I t ≤ Φ θ ,h ,t , (x ) -Φ θ ,h ,t , ( x ) dπ θ ,h ,t (x , x , ) dθ ≤ C ξ |x -x | dπ θ ,h ,t (x , x , ) dθ ≤ C ξ |θ |x -x| +| x -x | dπ θ ,h ,t (x , x , ) dθ , where x = θ |xθ + x and x = θ | xθ + x. Thus, I h ,t -I t ≤ C |u -ū | dγ θ ,h ,t (u, ū, ) + |x -x | d πθ ,h ,t (x , x ) dθ ≤ C SW (µ h t , µ t ) +W (µ h t , µ t ) . As supp ξ ⊂ [, T ] × B(, r ), ∞ I h n ,t -I t dt ≤ C T W (µ h n t , µ t ) dt ,
and since W (µ h n t , µ t ) tends to zero, by Lebesgue's dominated convergence theorem we get

I t dt ∼ I h n ,t dt, which means ∞ ψ t ,θ (θ | x) θ |∇ξ (t , x ) dθ dµ t ( x ) dt ∼ n→∞ ∞ ψ h n t ,θ (θ |x) θ |∇ξ (t , x ) dθ dµ h n t (x ) dt . Recall µ h n t is constant on each interval [kh n , (k +)h n ); hence, ∞ ψ t ,θ (θ | x) θ |∇ξ (t , x ) dθ dµ t ( x ) dt ∼ n→∞ h n ∞ k= ψ h n kh n ,θ (θ |x) θ |∇Ξ n k (x ) dθ dµ h n kh n (x ),
where we have set

Ξ n k (x ) := h n (k+)h n kh n ξ (t , x ) dt . However, ∇ξ (kh n , x ) -∇Ξ n k (x ) ≤ h n (k+)h n kh n ∇ξ (kh n , x ) -∇ξ (t , x ) dx dt ≤ C ξ h n , so, since ξ n k (x ) := ξ (kh n , x ), ∞ ψ t ,θ (θ | x) θ |∇ξ (t , x ) dθ dµ t ( x ) dt ∼ n→∞ h n ∞ k= ψ h n kh n ,θ (θ * ) θ |∇ξ n k dθ dµ h n kh n . (...b)
. Using to proposition .. on page and proposition .. on page and the optimality of µ h kh , if φ h k denotes the Kantorovich potential between µ h kh and µ

h (k -)h , h n ∇φ h n k ∇ξ n k dµ h n kh n = - ψ h n kh n ,θ (θ * ) θ |∇ξ n k dθ dµ h n kh n .
Let γ be an optimal transport plan between µ h kh and µ h (k -)h ; then, ξ n k (x )

ρ h n kh n (x ) -ρ h n (k -)h n (x ) h n dx = h n ξ n k () -ξ n k (x ) dγ (x , ), h n ∇φ h n k (x ) ∇ξ n k (x ) dµ h n kh n (x ) = - h n ∇ξ n k (x )| -x dγ (x , ).
and, since

ξ n k () -ξ n k (x ) -∇ξ n k (x )| -x ≤ C |x -| , ξ n k () -ξ n k (x ) -∇ξ n k (x )| -x dγ (x , ) ≤ CW µ h n (k -)h n , µ h n kh n ; so, using (...c), we get ξ n k (x ) ρ h n kh n (x ) -ρ h n (k -)h n (x ) h n dx + ψ h n kh n ,θ (θ * )θ |∇ξ n k dθ dµ h n kh n ≤ Ch n .
This immediately yields . Open questions ... The rst and main question that still need to be investigated, is the convergence of µ t toward the target measure ν when t tends to innity. When working with discrete measures only, we should not expect any convergence, as symmetry is preserved by the algorithm and a discrete solution might require it to be broken. Nonetheless, convergence might still happen when the measures are absolutely continuous.

h n ∞ k= ψ h n kh n ,θ (θ * ) θ |∇ξ n k dθ dµ h n kh n ∼ n→∞ - ∞ k= h n ξ n k (x ) ρ h n kh n (x ) -ρ h n (k -)h n (x ) h n dx (
The rst step toward convergence could be to study the stationary points. We know from theorem .. on page that

∂µ t ∂t + div( t µ t ) = with t (x ) := - S d - ψ t ,θ (θ |x)θ dθ .
But, does ψ t ,θ (θ * )θ dθ = implies µ t = ν? An answer can easily be given though, if µ t is absolutely continuous with a strictly positive density:

... Lemma. For any µ ∈P(B(, r )), if µ is absolutely continuous with a strictly positive density, then µ = ν if and only if As the sliced Wasserstein distance is a distance, this implies µ = ν.

... Another question, although a less important one, regards uniqueness. To obtain the generalized minimizing movement (µ t ) t ≥ , we have used the compactness of P (B(, r )) so many times, that there could be a great number of such curve for any given starting point µ and any target measure ν . For gradient ows in the space of probability measures, uniqueness often comes from the convexity of the functional.

Chapter . Isotropic IDT algorithm

However, like the usual Wasserstein distance, it is not dicult to show the sliced Wasserstein distance is -concave along geodesics: if (µ t ) is a geodesic between µ and µ , then

SW (µ t , ν ) ≥ ( -t )SW (µ , ν ) + tSW (µ , ν ) -t ( -t )W (µ , µ ) .
This does not prevent uniqueness, but if there is only one possible curve (µ t ), we will have to prove it by other means. Ceci revient à dire qu'un déplacement suivant l'axe vertical (nord-sud) coute moins qu'un déplacement suivant l'axe horizontal (est-ouest). La solution au problème du transport optimal pour le cout c t est encore donnée par une application, que l'on notera T t . Pour t = , il s'agit bien entendu de l'application de M. Brenier ; pour t ∈], ], cette application est aussi reliée à un potentiel de Kantorovitch S t via la relation Un changement de variable donne alors une équation de Monge-Ampère :

Synthèse

T t (x ) = x -A - t ∇S t (x ) avec A t =        t        . MM.
f (x ) = (x -∇S t (x )) det I -A - t ∇ S t (x ) .
Appliquer le théorème des fonctions implicites permet d'obtenir que t → S t est régulière, et dériver l'équation de Monge-Ampère donne alors une équation aux dérivées partielles :

div f I d -A - t ∇ S t -A - t ∇ Ṡt -Ȧt A - t ∇S t = . (d)
Cette équation devient cependant singulière lorsque t s'annule, puisque A - t est une matrice diagonale dont les coecients font intervenir /t.

Ce problème de singularité peut cependant être contourné en faisant un développement de S t au premier ordre vis-à-vis du paramètre t. Supposons que nous soyons en dimension deux ; puisque l'application T t = Id -A - t ∇S t converge vers le réarrangement de Knothe-Rosenblatt, et que celui peut s'écrire T K (x , x ) = (T K (x ), T K (x , x )), nous écrirons S t (x , x ) = u t (x ) + t t (x , x ).

Cette

  Optimal transportation . The Monge-Kantorovich problem .................... . Solution on the real line .......................... . Yann Brenier's map and its regularity .................. . Extension to the torus ........................... . The Wasserstein space ..........................

Figure A :

 A Figure A: Construction of the optimal map T in . The cumulative distributions, F and G, represent the areas below the graphs of the densities of µ and ν , denoted by f and respectively; the point x is sent onto , i.e. = T (x ), if and only if F (x ) = G (), which means the lled areas should be equal.

  [] and John Urbas [] from a theoretical point of view, and by Grégoire Loeper and Francesca Rapetti [] for numerical computations.

  Let us again denote by f and the densities of our two measures, µ and ν , on R . Given any orthonormal basis (e , e ), we can dene fe (x ) := f (x e + x e ) dx and e ( ) := ( e + e ) dx . Those are similar to the f and dened in the rst step of the construction of the Knothe rearrangement; they are, in fact, the same when e is the canonical basis, e = (, ) and e = (, ). Then, we have two unidimensional measures, so we know how to send one onto the other-thanks to the map T e = Ĝe • Fe , where Fe and Ĝe denote again the cumulative distributions. This map should also be a good indicator of how we need to move the original measure µ along the direction e to get ν . Likewise, we can get a map T e for the direction e , and then combine those two maps into T e (x ) := T e (e |x) e + T e (e |x) e (c) It is important to say, however, that this T e does not send µ onto ν . It sends µ onto another measure-let us denote it by µ -, which should nevertheless be closer to ν .

  Gigli, and Giuseppe Savaré []-with what Marc Bernot called the sliced Wasserstein distance as the functional, SW p (µ, ν ) = SW p ( f , ) := W p ( fe , e ) p de /p , the usual Wasserstein distance being the pth root of the minimum value of the Monge-Kantorovich problem for the cost c (x , ) = |x -| p :

  lecture notes []. For a more abstract and more general exposition, see also the monograph by Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré [, chapters -]. . The Monge-Kantorovich problem ... Monge's problem. Given two probability measures µ and ν on R d and a cost function c : R d × R d → [, ∞], the problem that was rst introduced by Gaspard Monge [] can be stated in modern terms as follows: nd T : R d → R d such that ν = T # µ and c (x , T (x )) dµ (x ) is minimal. (...a)

  P. Let µ, ν be two Borel probability measures on R d . If the cost function c : R d × R d → [, +∞) is lower semicontinuous, then there is a solution to the Monge-Kantorovich problem (...a). We denote by Γ o (µ, ν ) the set of all such solutions.

  and ψ dµ + φ dν is maximal. (...b) ... Kantorovich potential and c-transform. Its seems natural to look for a solution of the new problem (...b) among the pairs (ψ , φ) that saturate the condition, and therefore satisfy

. . .

 . In dimension one-that is, when µ and ν are probability measures on the real line-, a solution to the Monge-Kantorovich problem (...a) can very often be explicitly computed, and turns out to be a solution of Monge's problem (...a) as well. As we will see in chapter , my computation of the solution relies on the unidimensional case.

  ... Regularity. The regularity of the Kantorovich potential, for an arbitrary cost, is also very dicult question. During the past decade, a lot of progress has been made: a quite general theorem has been obtained by Xi-Nan Ma, Neil S. Trudinger, and Xu-Jia Wang []; a more specic result, on products of spheres, has been recently proved by Alessio Figalli, Young-Heon Kim, and Robert J. McCann []. Fortunately, chapter does not require a very abstract theory: all we need is contained in the next theorem ( §.., on page ), based on Dario Cordero-Erausquin's pioneering work []. It gives the existence and regularity of the Kantorovich potential Dario Cordero-Erausquin [] had already provided an extension to periodic measures. On a Riemannian manifold M, for any ∈ T x M, the point exp x () is dened as the value at time of the geodesic starting from x with initial velocity .

  therefore, T induces a dieomorphism T d → T d . ... P. Let µ and ν be two probability measures on T d with smooth, strictly positive densities, and let c be the quadratic cost on T d × T d induced by a denitepositive, symmetric matrix A. Then there is a unique c-concave function ψ : T d → R with ψ dµ = such that T : T d → T d dened by T (x ) := x -A -∇ψ (x ) sends µ onto

  Lebesgue dierentiation theorem, this shows that | μ | exists almost everywhere, | μ | = e, and since W p (µ t , µ t+h ) ≤ [t ,t+h] , this also shows | μ |≤.

.

  The case X = R d directly follows from lemma .. on the current page, equality being reached with a constant speed geodesic. Let us nevertheless give a demonstration for X = T d , inspired from the original article by Jean-David Benamou and Yann Brenier [], and the aforementioned book by Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré [, Chapter ]. The reader may also refer to a proof by Kevin Guittet [].

  and h, seen as a function of u, and w, is a smooth tame map, then there are U ⊂ U an open neighborhood of u , V ⊂ V an open neighborhood of , and a smooth tame map

tu

  (s) r +q ds ≤ Ce qt t e r s x (s) ds ≤ Ce qt r . (...a)

  ... P. Let M be a compact Riemannian manifold. Then C ∞ (M ) is a tame space.Proof. According to Nash's embedding theorem, M can be isometrically embedded into a bounded subset of R d , for some d ∈ N. Thanks to Whitney's extension theorem, C ∞ (M ) can therefore be tamely embedded into C ∞ (B), which is a tame space according to lemma .. on page .ChapterFrom Knothe's rearrangement to Brenier's optimal map ... A few years ago, Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio [] proved the existence of a connection between the Knothe-Rosenblatt rearrangement (which will be dened in §..) and Yann Brenier's map, in the form of a dierential equation-at least, when one of the two measures is discrete. In this chapter, I extend their result to the case of absolutely continuous measures. Most of what follows is taken from my article [].

  ... The Knothe-Rosenblatt rearrangement. This transport map was dened in the s, separately by Murray Rosenblatt [] and by Herbert Knothe []. The former had in mind applications to probability theory and statistics; the later used it to study convex bodies and prove an improved isoperimetric inequality -an idea later popularized by Mikhail Gromov [].

  and only if u is the Kantorovich potential between µ and ν for the cost induced by A.

  If we use the shorthand ∂u := (∂ u ,∂ u ), then T K = Id -∂ϕ, andG(, u , u ) = f -(Id -∂u) det (I -D∂u) . (...b)Thus, we can just take ψ := ϕ and ψ := ϕ .... Lemma. For any (t , u , u ) ∈ Ω, we have G(t , u , u ) = if and only if u = ψ t and u = ψ t .

  ..a) Proof. Let us assume (...a) has been proved for some n ∈ N, and let us show it holds even for n +. Let ν ∈ N be such that |ν | := ν + ν = n +. Recall (...g):

Figure . :

 . Figure .: When χ = tan θ is rational, we can work on a bigger torus.

  When both the source and target measures are discrete, many algorithms already exist for computing the solution to the optimal transport problem, the most famous perhaps being the auction algorithm due to Dimitri Bertsekas []. This algorithm was also used by Damien Bosc [] to deal with continuous measures, by approximation. When only one of the two measures is discrete, Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio [] showed the optimal transport map could be computed by solving an , starting from the Knothe-Rosenblatt rearrangement. In the general case, Jean-David Benamou and Yann Brenier [] proposed a method based on their formula (see theorem .. on page ). Sigurd Angenent, Steven Haker, and Allen Tannenbaum [] developed a steepest-descent algorithm, also starting from the Knothe-Rosenblatt rearrangement. Grégoire Loeper and Francesca Rapetti [],

  ...c) under the conditions Un+ (x ) dx = and Vn+ (x , x ) dx = . (...c) The last requirement can be a bit dicult to enforce numerically. However, the following lemma allows us to get Un+ and Vn+ from any pair ( ¯U n+ , ¯V n+ ) solving (...a):

Algorithm . :

 : Computation of the potential for Brenier's map, T B = Id -∇(U + V ) by looking at its variational formulation u ∈ arg min ∈H A∇ |∇q .

Figure . :

 . Figure .: The density is f (x , ) = ( + sin(πx )/)( + sin(π)/). Left: initial density.Right: density reconstructed using the computed potential. The error in L is ε = .%.

Figure . :

 . Figure .:As the density is a tensor product, the Knothe rearrangement (gray) is already optimal: nothing changes much, the result of the computations (black) is close.

Figure . :

 . Figure .: The density is f (x , ) = -(cos(πx ) + cos(π))/. Left: initial density. Right:density reconstructed using the computed potential. The error in L is ε = .%.

Figure . :

 . Figure .: The density is f (x , ) = + sin(πx ) sin(π)/. Left: initial density. Right:density reconstructed using the computed potential. The error in L is ε = %.

Figure . :

 : Figure .: Since f (x , ) d = for any x, the Knothe rearrangement (gray) has a zero rst component ; this is not the case with Brenier's map (black).

Figure . :

 . Figure .: Two gaussians, turned periodic. Left: initial density. Right: density reconstructed using the computed potential. The error in L is ε = .%.

Figure . :

 . Figure .: The Knothe rearrangement (gray) was not symmetric; Brenier's map (black) is.

  and set µ n+ := T n# µ n . Then e n i *# µ n+ = e n i |T n # µ n = [t e n i • e n i * ] # µ n = e n i *# ν . Thus, µ n+ should be closer to ν than µ n .... T(Pitié-Kokaram-Dahyot). We assume µ is absolutely continuous, and ν is a Gaussian measure. Then, . If B n are independent, uniform random variables on the set of all orthonormal basis, i.e. on O(d ), then µ n → ν almost surely.

  The basis e n = (e n ,...,e n d ) changes at each iteration.... Lemma. Let P σ denote the permutation matrix associated to a permutation σ , dened byP σ δ k = δ σ (k ) . Then, y σ = (I d ⊗P - σ )y. If σ θ is the optimal permutation between θ * # µ ∼ (θ * ⊗ I N )x and θ * # ν ∼ (θ * ⊗ I N )y ∼ (θ * ⊗ I N )y σ θ , we have

  ... To remove the dependence vis-à-vis the bases e n , Marc Bernot suggested to replace F e withF (x, σ ) := S d - (θ * ⊗ I N )(xy σ θ ) dθ , dened for x ∈ (R d ) N and σ : S d -→ S N .In other words,F (x, σ ) = d O(d )F e (x, (σ e ,...,σ e d )) de.

  then x is called a generalized minimizing movement (). ... The concept of minimizing movements was introduced by Ennio De Giorgi [], and developed furthermore by Luigi Ambrosio []. It is a fundamental tool for the theory of gradient ows in metric spaces, as developed by the latter with Nicola Gigli and Giuseppe Savaré [, ].

  ...c) . Combining (...a), (...b), and (...c), we get the result.

  |x)θ dθ = for µ-a.e. x , with ψ θ the unidimensional Kantorovich potential between θ * # µ and θ * # ν . Proof. If µ = ν , obviously the integral is zero. Conversely, let Ψ(x ) := S d - ψ θ (θ |x) dθ .

  Beaucoup d'illustrations ont déjà été proposées pour présenter simplement le problème du transport optimal. On a pu parler de tas de sables à déplacer[, ], de cafés parisiens à fournir en pain [], de charbon à amener depuis les mines jusqu'aux centrales électriques [], etc. Dans un soucis d'originalité, qu'il soit permis d'ajouter à cette liste l'exemple suivant. Il existe en Chine de gigantesques complexes industriels, regroupant plusieurs centaines de milliers d'ouvriers sur quelques kilomètres carrés []. Ceux-ci sont logés sur place, dans des dortoirs. Dans un soucis d'ecacité, il convient donc d'attribuer à chaque ouvrier un lit qui ne soit pas trop éloigné de son lieu de travail. Admettons qu'assigner à quelqu'un travaillant sur la ligne de montage x un lit dans le dortoir engendre pour l'entreprise un cout c (x , ), correspondant par exemple aux frais de fonctionnement d'un système de navettes. Quelle est alors la meilleure manière de loger tous les employés ? La répartition des travailleurs et celle des lits peuvent être représentées par deux mesures µ et ν, de sorte que µ(A) représente le nombre d'ouvriers travaillant dans la zone A et ν(B) le nombre de lits disponibles dans la zone B. Supposons qu'il n'y ait pas de logements superus, et que la capacité des dortoirs corresponde exactement aux besoins d'accueil ; cela se traduit par l'égalité dµ(x ) = dν(). Nous pouvons donc considérer que µ et ν sont des mesures de probabilité. La solution à notre problème est à rechercher sous la forme d'une mesure de probabilité γ sur l'espace produit, telle que γ(A × B) donne le nombre -ou plutôt, la proportiond'ouvriers travaillant dans la zone A et logeant dans la zone B ; ceci implique que µ et ν doivent être les marges de γ : µ, ν) l'ensemble de ces mesures γ, appelés « plans de transport ». Le déplacement quotidien des ouvriers entre leur dortoir et leur poste de travail entrainera alors toujours une dépense au moins égale à inf γ∈Γ(µ ,ν) c (x , ) dγ(x , ). (a) Il n'est pas dicile de montrer que cet inmum est toujours atteint : il existe toujours au moins un plan de transport γ correspondant à une allocation optimale des lits. Il est cependant très dicile de caractériser a priori les solutions ; l'enjeu est justement de calculer un plan γ optimal. C'est à Leonid Kantorovitch, mathématicien soviétique et récipiendaire du prix Nobel d'économie en , que l'on doit cette formulation du problème du transport optimal -non pas en termes d'ouvriers, mais de mesures de probabilité. Pour continuer dans la veine industrielle chinoise, Kantorovitch a montré dans les années quarante [, ] que le problème pouvait en quelque sorte être transféré sur les employés. Il sut en eet de leur faire porter le coût du transport, de leur faire payer un loyer pour leur logement, et de compenser cela pour eux par une subvention. Il ne s'agit pas de gagner de l'argent ainsi, mais d'inciter les ouvriers à trouver eux-même le lit le mieux placé ; le prix du transport sera donc égal à son cout de fonctionnement c (x , ). Notons S(x ) la subvention accordée aux employés de la chaine de montage x, et L() le loyer d'un lit dans le dortoir ; Kantorovitch a montré que la valeur des subventions S et celle des loyers L peuvent être xées judicieusement, de telle sorte que : -les travailleurs reçoivent toujours moins que ce qu'ils ont à dépenser, c'est-à-dire S(x ) L() + c (x , ) quels que soient x et ; -chaque ouvrier peut cependant trouver un lit idéal qui ne lui fera pas perdre d'argent, pour lequel S(x ) = L() + c (x , ) ; -il est possible que les employés réussissent tous à trouver un lit idéal. Kantorovitch a montré que, dans ce cas, le cout total de l'opération pour l'entreprise, qui est donné par la diérence entre le montant total des subventions et la somme récupérée par les loyers, est alors S(x ) dµ(x ) -L() dν() = min γ∈Γ(µ ,ν) c (x , ) dγ(x , ). Les potentiels S et L sont alors appelés des « potentiels de Kantorovitch ». Notons que si les chaines de montages sont de petits ateliers qui ne sont pas trop concentrés, il est envisageable que les ouvriers travaillant ensemble en x puissent se retrouver dans le même dortoir = T(x ). Une telle application T fait alors correspondre µ et ν, ce qui se traduit par ν(B) = µ(T -(B)) quel que soit B, ou encore ξ() dν() = ξ(T(x )) dµ(x ) ; on dit alors que T envoie µ sur ν, et l'on note ν = T # µ. Notons qu'à une telle application est associé un plan de transport γ T , déni par γ T (A × B) = µ(A ∩ T -(B)). L'intuition que le transport optimal prend la forme d'une telle application si la source est susamment diuse se traduit mathématiquement par un résultat démontré par Yann Brenier [, ] à la n du e siècle : si le cout de transport est égal au carré de la distance, c (x , ) = |x -| , et si µ est absolument continue, alors il existe uneapplication T envoyant µ sur ν qui résout le problème du transport optimal, c'est-à-dire que le plan de transport γ T est optimal, et le coût total de transport estmin γ∈Γ(µ ,ν) c (x , ) dγ(x , ) = c (x , ) dγ T (x , ) = c (x , T(x )) dµ(x ).De plus, les potentiels de Kantorovitch S et L sont alors reliés à l'application T par les relations= T(x ) = x -∇S(x ) et x = T -() = + ∇L().Celles-ci traduisent le fait que, pour trouver un logement, il est intéressant d'aller dans la direction des subventions décroissantes, puisque les subventions sont moindres lorsque des dortoirs sont proches. Inversement, des loyers plus élevés signalent une plus grande demande, et donc un plus grand nombre d'ateliers. Le résultat de M. Brenier résout ainsi un problème ancien, posé d'abord par Gaspard Monge [] à la n du e siècle. Celui-ci avait en eet essayé de résoudre le problème du transport optimal en cherchant la solution, non pas sous la forme d'un plan de transport γ comme Kantorovitch plus tard, mais sous la forme d'une application T. Le coût total de transport est alors au minimum inf ν=T # µ c (x , T(x )) dµ(x ). (b) Puisque chaque application T qui fait correspondre µ et ν donne un plan de transport γ T , le problème de Kantorovitch (a) est en fait une extension du problème initial de Monge (b). Cependant, à l'inverse du premier, le second peut ne pas avoir de solution ; il peut même ne pas y avoir d'application T telle que ν = T # µ, par exemple si µ est discrète et que ν est uniforme. Mais si µ est absolument continue, et pour un coût quadratique, l'application de M. Brenier est solution du problème de Monge, et résout aussi le problème de Kantorovitch. Il faut noter qu'en dimension un, il est très facile de résoudre le problème de Monge. S'il l'on note par F et G les fonctions de répartition de µ et ν respectivement, F(x ) := µ(] -∞, x]) et G() := ν(] -∞, ]), alors la solution au problème de Monge pour n'importe quel cout strictement convexe, c'est-à-dire n'importe quel cout déni par c (x , ) = h(x ) avec h positive et strictement convexe, est T(x ) := G -(F(x )). (c) En dimension plus grande, il est beaucoup plus dicile de calculer cette solution. Quelques méthodes ont cependant été développées au l des années : -lorsque les mesures de départ et d'arrivées sont discrètes, un algorithme célèbre a été mis au point par Dimitri Bertsekas []; -cet algorithme a ensuite été utilisé par Damien Bosc [] pour traiter le cas de mesures continues, par approximation ; -toujours dans le cadre continu, Jean-David Benamou et Yann Brenier [] ont aussi proposé une méthode, basée sur une interprétation en termes de mécanique des uides ; -Sigurd Angenent, Steven Haker et Allen Tannenbaum [] ont, eux, réussi à utiliser une méthode de descente de gradient ; -enn, Grégoire Loeper et Francesca Rapetti [] ont pu utiliser avec succès la méthode de Newton. Il y a quelques années, Guillaume Carlier, Alfred Galichon et Filippo Santambrogio [] ont cependant proposé une nouvelle méthode pour calculer l'application optimale de M. Brenier. Leur approche repose sur l'introduction d'un paramètre t ∈ [, ] dans la fonction de cout : par exemple, en dimension deux, c t (x , ) = |x , | + t |x -| .

  T K (x , x ) := (T K (x ), T K (x , x )). Contrairement à l'application de M. Brenier, ce réarrangement est donc très facile à calculer explicitement. MM. Carlier, Galichon et Santambrogio ont pourvé que, lorsque l'une des deux mesures est discrète, l'évolution de l'application T t entre le réarrangement et l'application de M. Brenier est guidée par une équation diérentielle.La première partie de cette thèse a été consacrée à l'extension de leurs résultats aux cas de mesures absolument continues. Le problème gagne alors notablement en complexité.Tant que t demeure strictement positif, il n'y a pas de grande diculté. Notons f et les densités respectives de µ et ν. Puisque T t (x ) = x -∇S t (x ) envoie µ sur ν, pour n'importe quelle fonction test ξ nous avons ξ()() d = ξ() dν() = ξ(T t (x ))µ(x ) = ξ(T t (x ))f (x ) dx .

  Une discrétisation explicite en temps permet alors d'obtenir les résultats présentés dans le chapitre . Dans la dernière partie de cette thèse, nous avons étudié l'algorithme (Iterative Distribution Transfer), développé par François Pitié, Anil C. Kokaram et Rozenn Dahyot []. Cet algorithme construit une application de transport susamment proche de celle de M. Brenier pour convenir à la plupart des applications []. Cependant, ses caractéristiques mathématiques sont encore assez mal connues. Considérons une mesure de référence ν sur R d de densité , et xons une mesure de départ µ de densité f , ainsi qu'une première base orthonormale e = (e ,...,e d ) de R d . Il est possible de projeter chacune des deux mesures sur les axes donnés par e ; nous obtenons ainsi d couples de mesures unidimensionnelles f i et i Cette application n'envoie pas µ sur ν, mais la mesure image µ := T # µ semble néanmoins plus proche de ν que µ . Nous pouvons alors choisir une suite de base (e n ) et, en répétant l'opération, construire une suite d'applications (T n ) et une suite de mesures (µ n ) telles que µ n+ := T n# µ n , où l'application T n a été construite à l'aide de la base e n , et les mesures µ n semblent alors se rapprocher empiriquement de ν si les bases (e n ) forment une suite dense dans l'espace des bases. La convergence mathématique n'a pu cependant être démontrée par MM. Pitié, Kokaram et Dahyot [] que dans le cas de mesures gaussiennes.Il se trouve que l'algorithme peut être interprété en termes de ot de gradients pour une fonctionnelle faisant intervenir une certaine distance. En eet, dans le problème du transport optimal, la valeur minimale du cout de transport induit une distance, appelée distance de Wasserstein, entre les deux mesures µ et ν ; notamment, lorsque ce cout est égal au carré de la distance euclidienne, on dénitW (µ, ν) := min Γ(µ ,ν) |x -| dγ(x , ).L'algorithme correspond alors à un schéma d'Euler explicite pour un ot de gradients pour la fonctionnelleF (µ) = d S d - W (θ # µ, θ # ν) dθ,où la fonctionnelle F est aussi discrétisée à chaque étape n et approchée parF (µ) ≈ d i= W (e n i # µ, e n i # ν) .Il se trouve queSW (µ, ν) := S d - W (θ # µ, θ # ν) dθ,dénit une nouvelle distance, appelée distance de Wasserstein projetée (ou distance de Super-Wasserstein), qui est équivalente avec la distance de Wasserstein usuellecomme je l'ai démontré dans le théorème .. (page ).Les dernières sections sont consacrées à l'étude du ot de gradients pour la fonctionnelle F dans l'espace des mesures de probabilité, au sens de la théorie développée par Luigi Ambrosio, Nicola Gigli et Giuseppe Savaré []. Ce ot, déni comme étant la limite d'un schéma d'Euler implicite pour F , pourrait en eet permettre de mieux comprendre le comportement de l'algorithme .

  and |det(Da k )|≥ε k µ n -a.e., see the book by Lawrence C. Evans & Ronald F. Gariepy [, Section ..]. Thus, if N is a negligible set for the Lebesgue measure, and ρ n stands for the density of µ n ,

  Carlier and Filippo Santambrogio [], and Giuseppe Buttazzo and Filippo Santambrogio []. It is well known the entropy H is lower semicontinuous for the Wasserstein distance (see, for instance, the article by Richard Jordan, David Kinderlehrer, and Felix Otto [, Proposition ]). Therefore, if (µ n ) n ∈N is a minimizing sequence in P (rB), then, up to an extraction, it converges toward a minimizer µ, which must necessarily have a density ρ.

  Let (µ t ) t ≥ be a generalized minimizing movement given by theorem .. on page . We denote by ρ t the density of µ t . As previously, let ψ t ,θ stand for the Kantorovich potential between θ * # µ t and θ * # ν such that ψ t ,θ dθ * # µ t = . Then, in a weak sense,

... T.

  Carlier, Galichon et Santambrogio ont montré que, lorsque t tend vers zéro, T t converge vers le réarrangement de Knothe-Rosenblatt. Ce « réarrangement », introduit dans les années cinquante séparément par Herbert Knothe [] et Murrey Rosenblatt [], envoie encore µ sur ν, et s'obtient par une succession de transformations unidimensionnelles. Par exemple, en dimension deux, si f (x , x ) et ( , ) sont les densités de µ et ν, alors (x ), t ) dtsont aussi deux mesures de probabilités ; si l'on note x → T K (x , x ) l'application envoyant l'une sur l'autre, alors le réarrangement deKnothe-Rosenblatt est

	x →	f (x , t ) dt	et	→	( , t ) dt
	sont deux mesures de probabilité sur la droite réelle, et nous savons comment envoyer
	K (x ) l'application la première sur la seconde, grâce à la formule (c) ; notons x → T ainsi obtenue. Alors,
	x →	f (x , x ) f (x , t ) dt	et	→	(T K (x ), ) (T

K

  décomposition est unique si l'on impose u t (x ) dx = S t (x ) dx et Il faut noter que l'aspect le plus délicat de cette étude lorsque t tends vers zéro provient alors d'une perte de régularité vis-à-vis de la seconde variable, qui empêche d'appliquer le théorème des fonctions implicites classique comme précédemment. Cette diculté peut être contournée en utilisant une version plus forte du théorème, due à John Nash et Jürgen Moser ; celle-ci nécessite néanmoins de ne plus travailler qu'avec des mesures extraordinairement régulières, absolument continues, strictement positives et de classe C ∞ . Il a cependant été possible d'utiliser cette méthode pour calculer numériquement le transport optimal. L'équation (d), où S t (x , x ) a été remplacé par u t (x ) +t t (x , x ), peut être décomposé, ce qui donne le système suivant : (x , x ) dx , div(A t ∇ t ) = q t , = det(∇ t ) + t div Co ∇ t * ∇ t , q t = det(∇ t ) -( -∂ , t )∂ , ut -∂ , t , Le potentiel S t = u t + t t n'étant déni qu'à une constante près, les deux équations suivantes peuvent être ajoutées : u t (x ) dx = et

		
	      p t avec ∂ , ut (x ) = 
	  	p t
	  

t (x ) dx = , car dans ce cas

u t (x ) := S t (x , x ) dx et s t (x , x ) := S t (x , x )u t (x ) t . Alors T t (x , x ) = Id -       ∂ u t (x ) + t∂ t (x , x ) ∂ u t (x , x )        ,

et l'équation (d) perd sa singularité. Elle peut alors être étudiée lorsque t tends vers zéro. Notons que ce raisonnement se peut transposer en n'importe quelle dimension d > . t (x , x ) dx = .

Acknowledgements

and

under the conditions u t (x ) dx = and t (x , x ) dx = .

(...d)

We therefore have four unknown-that is, u t , t , ut , t -and four equations, given by (...b) and (...d).

... Discretization. We proceed with an explicit discretization with respect to time. Given a time step h > such that /h ∈ N, we compute four sequences of maps:

(U n ) and ( Un ), depending only on the variable x , and (V n ) and ( Vn ), depending on x and x . The maps U n and V n will represent u nh and nh , and Un and Vn will represent unh and nh , for n ∈{,...,/h}. To that end, we rst set

The values of U and V are, in fact, of no consequence. Then, by induction, given the values of U n , Un , V n , Vn , we solve

and

.

Open questions

In order to have a proper evaluation of this method, four questions need to be addressed:

. Where do the artifacts come from? Why do they appear on the left and right boundaries, whilst the domain is periodic? An explanation might come from our using an explicit discretization in time; an implicit discretization would probably better, but the computations would become a lot harder.

. Those numerical experiments presented here were always obtained for a uniform target measure. Is it possible to deal with more general situations? In that case, both the dierential equation and the initial condition satised by the Kantorovich potential are much more complex, and may need to be carefully handled.

. Does this method give better results than other algorithms? It would be specially interesting to compare it with the methods of Sigurd Angenent, Steven Haker, and Allen Tannenbaum [] on the one hand, and Grégoire Loeper and Francesca

Rapetti [] on the other, since both compute the optimal transport map as well. A comparison with the method of Jean-David Benamou and Yann Brenier [], which computes the geodesic rather than the optimal map, would be less straightforward.

. At last, numerical convergence and numerical stability are two crucial issues that have been left entirely untouched.