Видео

Yes, good catch!

This formulation requires computing the cost c(x,y) between ALL possible pairs of points x and y. There are no unknowns in this step. Then the unknown pi(x,y) (the transport plan) essentially multiplies this and determines how much weight is assigned to each pair (i.e. how much mass is moved from x to y).

I was using Trench, Introduction to Real Analysis, which is freely available online.

@@brittanyhamfeldt Thanks for your prompt reply as I have it

Yes, entropy regularisation would still apply in this setting. And good observation - L1 based minimisation tools are certainly reasonable for trying to capture the sparsity.

@@brittanyhamfeldt Thank you professor.

Unfortunately I don't have any clean lecture notes available.

We used the continuity equation in a previous lecture on the "Benamou-Brenier Formulation", and showed how to connect this to optimal transport. Now we are looking at gradient flow schemes and trying to show that they can be interpreted as a similar kind of flow satisfying a continuity equation, which requires some v in order to be fully defined.

Continuity equation is is just "mass conservation" saying that the time rate of change at a specific location must be balanced by the flux coming in and out (the divergence term involving vector field). The gradient flow here must satisfy continuity because we are transporting pdf whose integral must always equal 1 ("the mass of the pdf must be conserved").

Yes, this would come next after Heine-Borel. There is a bit of intermediary material on limits assumed (but, unfortunately, not recorded due to technical issues), but this is not essential if you have taken a first course on analysis.

Good catch, thanks!

sounds cuts out around 33.45 and doesn't come back until around 1:06:48 ☹

Thanks for letting me know. It appears, unfortunately, that the microphone died at that point, and there is a period of silence before they were able to switch over to the backup.

Yes - good observation!

No, we don't need to know the value (and often don't in practice), we just need to be able to assert that such a value L exists.

Unfortunately I don't have any notes available at this time. For practice problems, I recommend the exercises in Trench, "Introduction to Real Analysis", which is freely available online.

We only needed to do this proof by contradiction argument one time: to prove that "mathematical induction" works. That is, we proved by contradiction that anytime the hypotheses hold (base step and induction step), then the conclusion automatically holds as well for all n. From this point on, we know that mathematical induction works. Given a particular problem, all we need to do is demonstrate that the hypotheses are true (base step and induction step). And then we are done: we are guaranteed that the conclusion holds for all n. There is no need for an additional proof by contradiction.

Indeed -actually, Villani wrote one of the main textbooks I used as a reference for this. (Topics in Optimal Transportation)

The missing ingredient here is that phi is convex. Let's restrict everything to the line segment in the direction -x_0 for simplicity. This is our setting: u(x) = 0 for all x < x_0 and phi(x_0) = 0 and phi"(x) >= 0 for all x. Now let's suppose that also phi(x)<0 for all nearby x < x_0. Taylor expand. Then for some c: 0 > phi(x) = phi'(x_0)(x-x_0) + phi"(c)(x-x_0)^2/2 >= phi'(x_0)(x-x_0) for all nearby x < x_0. Since there is a strict inequality involved, it must be the case that phi'(x_0) is not equal to 0.

@@brittanyhamfeldt ohhhh thank you very much professor!!

Hi, I'm not sure if I'm 100% understanding the question correctly so feel free to follow up. Indeed, we end up inverting the transform with respect to x in order to write down a candidate velocity field. Then you can verify directly that v(t, X(t,x)) = (T-I) (y^{-1}(y(x))) = T(x) - x, which ensures that X(1,x) coincides with the optimal map. Note that if f and g are nice enough, then the Jacobian of T is positive definite (T is the gradient of a convex function) and so is the Jacobian of y.

@@brittanyhamfeldt Thanks for the answer, The problem is that I'm not finding the Jacobian in the integral after the variable substitution.

@@yacinemokhtari7531 This is where we make the substitution s(x) = X(t,x)? Here I am not using the change of variables formula, I am using the fact that s # f = ho One way of characterizing the pushforward is that \int \phi(y) ho(y) dy = \int \phi(s(x)) f(x) dx for every continuous compactly supported function \phi(y).

Thank you Brittany for the clarifications. Great lectures

Same! Her OT videos helped me a lot

Indeed, u depends on epsilon, and you need to appeal to stability of the Kantorovich potential in order to fill in the details. I recommend Santambrogio's book (section 7.2) for a more detailed discussion of the first variation.

@@brittanyhamfeldt thanks for the ref. Great lectures by the way :)

Great question, this actually does not work in Rd. For example, let's consider 2 linear maps T(x) = Ax, S(y) = By with A and B both symmetric positive definite. These are cyclically monotone since they can be written as the gradient of a convex function (1/2 * x^TAx and 1/2 * y^TBy respectively). Consider the composition of the maps: R(x) = S(T(x)) = BAx. In general, the matrix product BA need not be symmetric and the map is not the gradient of any function (much less a convex one), thus not cyclically monotone.

@@brittanyhamfeldt Thanks for the clarification, it makes sense! I have a follow-up question. In that case, is the composition of two optimal transport maps still optimal (assume all involved measures are absolutely continuous, supported on compact sets, and use quadratic cost in Monge formulation)? I have this question because of the equivalence between cyclical monotonicity and optimality of transport map, c.f. Brenier-McCann theorem.

@@Ethan-lz5rw Indeed, a consequence of this is that the composition of two optimal maps is NOT optimal in general.

@@brittanyhamfeldt Thank you!

Yes, that's a typo - good catch!

The proof is in this paper: www.intlpress.com/site/pub/files/_fulltext/journals/cms/2016/0014/0008/CMS-2016-0014-0008-a009.pdf Feel free to reach out via e-mail if you have trouble viewing it on the journal's website.

I recommend at least a good background in analysis/measure theory. Some exposure to other topics such as calculus of variations, numerical analysis may be helpful but probably isn't required.

@@brittanyhamfeldt thank you.

Here F is a functional on the space of probability measures, so when we compute its first variation we expect to get another functional, which will act on the functions Chi through an integral to produce a real number.

This is meant to be an example showing that we cannot expect to get smooth solutions in general. Remember: the solution of a PDE depends on both the PDE and the boundary conditions. So phi(x,y)=1/2 x^2+1/2y^2 is actually not the solution in this case, since it violates the boundary condition. I don't know an explicit formula for the solution of the Monge-Ampere equation with this Dirichlet boundary condition. But, we can certainly argue that it cannot be smooth up to the boundary. That is the motivation here: to show that smooth solutions may not be possible.

Good question! I may never have stated it explicitly in this lecture, but it comes from showing that we can extract a measure-preserving map from the minimisation problem. The arguments are identical to those in the lecture on "Charcterising the Optimal Map". There we made the assumption that \mu and u are sufficiently nice in that they don't give mass to sets of measure 0. This allowed us to represent the optimal maps as an (a.e.) gradient of a convex function, and only integrate over the subsets \tilde{X} or \tilde{Y} where they are differentiable. We don't lose out on anything by doing this since the sets of non-differentiability have measure-zero and do not have any mass. In the polar factorisation theorem, the identical arguments go through if we choose \mu to be the Lebesgue measure and u = r # \mu (the pushforward measure). The statement that r is non-degenerate is equivalent to saying that u does not give mass to sets of Lebesgue measure zero.

Great question, bounds on \psi follow from it's definition as a L-F transform of \phi (and the boundedness of the domains). So we get |\psi| \leq sup |X| * sup |Y| + \sup |\phi|

Thanks for the question! It's not something I'd thought about before. Here is my initial (hand-waving) attempt at an answer. If I understand your question correctly, let us suppose that we are given measures \mu_1 and \mu_2, with the optimal map between them given by T. Now for some real-valued \lambda, let us define the new mapping T_1(x) = \lambda x + (1-\lambda) T(x) and the new measure \mu = T_1 # \mu_1. The question then is, is T_1 the optimal map from \mu_1 to mu? Let's assume everything is smooth enough that we can represent the optimal map T as the gradient of a convex C^2 function u, T = abla u. Then T_1(x) = abla ( \lambda |x|^2 / 2 + (1-\lambda) u ) = abla \psi(x) Is this optimal? It is if the potential function \psi is convex. Check the Hessian: D^2\psi(x) = \lambda I + (1-\lambda) D^2u(x) This is certainly positive semi-definite for \lambda \in [0,1]. Since we've assumed here smoothness of the Hessian, it will also be positive definite for a range of values of \lambda > 1. If, moreover, us is uniformly convex (so D^2u(x) is strictly positive definite), \psi should also be convex for some values of \lambda < 0 (as long as they are not too large in magnitude). So the answer to your question seems to be yes: if things are "nice enough", we can extrapolate a little ways and still obtain an optimal map.

@@brittanyhamfeldt Thank you a lot professor for taking time on my question! I like this result a lot. Not only because we now know the extrapolability is controlled by the eigenvalues of D^2u, but also we know that for nondegenerate case, there is always a strictly positive margin that we can extend this geodesic segment while still being on the same geodesic. Thank you again!