This is so precise, I like the fact that you went on and explained Dirac mass... and the discrete, continuous aspect of it. Thank you for the amazing free content.
Dear Professor Hamfeldt, Many thanks from Germany - for uploading the lecture series on Optimal Transport! I need to understand this subject in order to work on my masters thesis on Mathematical Imaging. Your videos provide a good understanding of the topic. Kind regards, Abhit
Thanks for sharing this nice introductory video. I have two questions: (1) why can we write the preservation of measure (on every measurable set) alternatively in the form given at @52:11? (2) For 1D Monge problem, do we assume that $T$ is continuous so that an open interval $I_1$ is mapped to another open INTERVAL $J_1$?
(1) As a quick sketch of the reasoning, imagine approximating a continuous function h by a piecewise constant function h_\epsilon. Then we can rewrite \int_Y h_\epsilon(y) g(y) dy as the sum of integrals over regions Y_j where h_\epsilon is constant. Then you can apply the fact that \int_{Y_j} g(y) dy = \int_{T^{-1}(Y_j)} f(x) dx and take \epsilon to 0 to obtain the alternate characterisation. If you want to show the alternate direction of the equivalence, you can let h^\epsilon be a constant function approximating a characteristic function of the set A. (2) In 1D, this argument can be generalised to the case where T is discontinuous (it just requires more careful bookkeeping). The optimal map T would be uniquely defined almost everywhere, and can certainly have discontinuities. For example, if your source mass f is supported on an interval and your target mass g is supported on a union of disjoint intervals the map would have to be discontinuous.
Dear Professor Hamfeldt, I dont understand why "T,T~ measure preserving" gives us the same integrals on I_1 \cup I_2, i.e. \int f(x)T^2 dx = \int f(x)T~^2. The definition for measure preserving has T only in the domain of the integral, but not in the integrand. Maybe you can help me out here. Thank you very much and Greetings!
Sure, this comes from the alternate way of characterising measure-preserving as \int_X h(T(x)) f(x) dx = \int_Y h(y) g(y) dy for every continuous function h. If T and \tilde{T} are both measure-preserving than we could take h(y) = |y|^2 (for example) and get that \int_X |T(x)|^2 f(x) dx = \int_Y |y|^2 g(y) dy = \int_X |\tilde{T}(x)|^2 f(x) dx For a quick sketch of why this works, imagine approximating a continuous function h by a piecewise constant function h_\epsilon. Then we can rewrite \int_Y h_\epsilon(y) g(y) dy as the sum of integrals over regions Y_j where h_\epsilon is constant. Then you can apply the fact that \int_{Y_j} g(y) dy = \int_{T^{-1}(Y_j)} f(x) dx or \int_{Y_j} h_\epsilon(y) g(y) dy = \int_{T^{-1}(Y_j)} h_\epsilon(T(x)) f(x) dx since h_\epsilon is constant on these regions. Then sum over all the j and take \epsilon to 0 to obtain the alternate characterisation.
Thanks for putting up these amazing materials. I have two quick questions, 1) if the transport problem is restricted in probability measure, wouldn't the product measure itself defines a measure preserving transform, hence the problem is well-posed (the set is non empty)? My intuition suggest this will be a terrible way of transporting, as we are "uniformly" redistributing the masses. 2) I am thinking if there is a connection to markov chain, as if we start with a probability measure over the states, there is a natural "push-forward" measure induced by transition function, and I can define a "transition measure" that satisfying the measure preserving property between the initial measure on states and the updated measure after one markov transition. I guess I might have to wait for later set of lectures to answer the question: is this transition measure the optimal transport (with respect square cost)?
1) Yes, for the Kantorovich problem you can easily construct a feasible transport plan, which takes care of existence of an optimal plan (though not uniqueness). The Monge problem is different: there may not be an example of a feasible transport map. For example, consider a source consisting of a single unit Dirac mass, and your target of two masses each with weight 1/2. A transport plan will allow mass from the source to be split in half, but you cannot accomplish this with a single-valued transport map. 2) Yes, in fact some methods (eg Benamou-Brenier) involve flowing your measure from the source to the target. Along the way you produce such intermediate measures as you propose.
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.
This is so precise, I like the fact that you went on and explained Dirac mass... and the discrete, continuous aspect of it. Thank you for the amazing free content.
Dear Professor Hamfeldt,
Many thanks from Germany - for uploading the lecture series on Optimal Transport!
I need to understand this subject in order to work on my masters thesis on Mathematical Imaging. Your videos provide a good understanding of the topic.
Kind regards,
Abhit
Have you finished your thesis yet?
At 38:23 shouldn't it be Total Mass coming from x not X? Great video btw, thank you
Yes, good catch!
Thanks for sharing this nice introductory video. I have two questions: (1) why can we write the preservation of measure (on every measurable set) alternatively in the form given at @52:11? (2) For 1D Monge problem, do we assume that $T$ is continuous so that an open interval $I_1$ is mapped to another open INTERVAL $J_1$?
(1) As a quick sketch of the reasoning, imagine approximating a continuous function h by a piecewise constant function h_\epsilon. Then we can rewrite
\int_Y h_\epsilon(y) g(y) dy
as the sum of integrals over regions Y_j where h_\epsilon is constant. Then you can apply the fact that
\int_{Y_j} g(y) dy = \int_{T^{-1}(Y_j)} f(x) dx
and take \epsilon to 0 to obtain the alternate characterisation.
If you want to show the alternate direction of the equivalence, you can let h^\epsilon be a constant function approximating a characteristic function of the set A.
(2) In 1D, this argument can be generalised to the case where T is discontinuous (it just requires more careful bookkeeping). The optimal map T would be uniquely defined almost everywhere, and can certainly have discontinuities. For example, if your source mass f is supported on an interval and your target mass g is supported on a union of disjoint intervals the map would have to be discontinuous.
Hello,Professor. May I ask you that, Do u have organized lecture notes for this course. would u like to share it ?
At 52:40, isn't h a continuous function on Y?
Yes, good catch!
Dear Professor Hamfeldt, I dont understand why "T,T~ measure preserving" gives us the same integrals on I_1 \cup I_2, i.e. \int f(x)T^2 dx = \int f(x)T~^2. The definition for measure preserving has T only in the domain of the integral, but not in the integrand. Maybe you can help me out here. Thank you very much and Greetings!
Sure, this comes from the alternate way of characterising measure-preserving as
\int_X h(T(x)) f(x) dx = \int_Y h(y) g(y) dy
for every continuous function h.
If T and \tilde{T} are both measure-preserving than we could take h(y) = |y|^2 (for example) and get that
\int_X |T(x)|^2 f(x) dx = \int_Y |y|^2 g(y) dy = \int_X |\tilde{T}(x)|^2 f(x) dx
For a quick sketch of why this works, imagine approximating a continuous function h by a piecewise constant function h_\epsilon. Then we can rewrite
\int_Y h_\epsilon(y) g(y) dy
as the sum of integrals over regions Y_j where h_\epsilon is constant. Then you can apply the fact that
\int_{Y_j} g(y) dy = \int_{T^{-1}(Y_j)} f(x) dx
or
\int_{Y_j} h_\epsilon(y) g(y) dy = \int_{T^{-1}(Y_j)} h_\epsilon(T(x)) f(x) dx
since h_\epsilon is constant on these regions.
Then sum over all the j and take \epsilon to 0 to obtain the alternate characterisation.
@@brittanyhamfeldt Thanks a lot!
Thank you for putting up interesting video. I learn a lot from through it
Very precise and clear instruction. Just wondering is this the same field of optimal transport that prof. Cedric villani works in.
Indeed -actually, Villani wrote one of the main textbooks I used as a reference for this. (Topics in Optimal Transportation)
Thank you very much for this well explained introduction.
Hi Dr. Hamfeldt, thank you very much for the great lectures! Do you have the lecture notes posted online by any chance?
Unfortunately I don't have any clean lecture notes available.
Thanks for putting up these amazing materials. I have two quick questions, 1) if the transport problem is restricted in probability measure, wouldn't the product measure itself defines a measure preserving transform, hence the problem is well-posed (the set is non empty)? My intuition suggest this will be a terrible way of transporting, as we are "uniformly" redistributing the masses. 2) I am thinking if there is a connection to markov chain, as if we start with a probability measure over the states, there is a natural "push-forward" measure induced by transition function, and I can define a "transition measure" that satisfying the measure preserving property between the initial measure on states and the updated measure after one markov transition. I guess I might have to wait for later set of lectures to answer the question: is this transition measure the optimal transport (with respect square cost)?
1) Yes, for the Kantorovich problem you can easily construct a feasible transport plan, which takes care of existence of an optimal plan (though not uniqueness). The Monge problem is different: there may not be an example of a feasible transport map. For example, consider a source consisting of a single unit Dirac mass, and your target of two masses each with weight 1/2. A transport plan will allow mass from the source to be split in half, but you cannot accomplish this with a single-valued transport map.
2) Yes, in fact some methods (eg Benamou-Brenier) involve flowing your measure from the source to the target. Along the way you produce such intermediate measures as you propose.
great lecture ! thank you
Hi, what math do I need to follow in this course?
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.
You're kinda dope though. Smooth, luxurious exposition. Bless.