Gromov-Hausdorff convergence of discrete optimal transport
Maas, Jan
For a natural class of discretisations of a convex domain in Rn, we consider the dynamical optimal transport metric for probability measures on the discrete mesh. Although the associated discrete heat flow converges to the continuous heat flow, we show that the transport metric may fail to converge to the 2-Kantorovich metric. Under an additional symmetry condition on the mesh, we show that Gromov-Hausdorff convergence to the 2-Kantorovich metric holds. This is joint work with Peter Gladbach and Eva Kopfer.
 It's a really great pleasure to be here. OK, so I would like to present some joint work. They're recent, so hopefully in the archive in a couple of days. And it's in collaboration with Peter Klaupach from Leitzig and Eva Kopper from Hul. So before stating the problem that we are studying, maybe let me write down something that everybody knows here. So that's the binomukul veneer problem for the system. Let's take the system metric in Rn to Rn. That's the formula expression. So w2 square rho n times rho 1 is the minimum of the kinetic energy which is needed to transport between rho n and nopart. So I integrate in time, integrate in space, d dx divided by rho dx dx dt where rho and v satisfy the continuity equation. So dt v plus the divergence v is 0 with boundary conditions. Not to the rho 1. OK, so this is the binomukul veneer formula, which is not the definition of Wasserstein, but it's, of course, equivalent in the continuous setting. What I'm interested in is this talk, is sort of discrete analogs of this metric. So they are not Wasserstein metric, but they are defined in terms of an analog of this binomukul veneer. So let me tell you about the discrete counterpart to this formula. And to define it, I need to start with the generator of a map of chain. So let L be the generator of a reversible mark of chain of a finite set x. And so L has the following form. So I have psi of x is the sum of y of qxy times psi of y times psi of x. For qxy are the transition rates of my mark of chain. So these are the numerical numbers. OK, so given such a generator of reversible mark of chain, I can define the object that I'm interested in, and that's the discrete transport metric by an analog of the binomukul veneer formula. So the mission for probability measures mu1 and mu0 to mu1 on x, I define a distance w, it's a corny w, square mu0 to mu1 as the epheymum following expression. So again, I integrate in time. And now the space integral will be this great sum, and ptxy square divided by something dt. And before I write something, I write the continuity equation. So this is subject to dt mu dx plus discrete divergence of v equal to 0. So this would be 1 half sum over y dtxy minus v2 by x equal to 0, which is the boundary condition mu times 0 and 1. It's given by mu1. OK, so as you see, I'm mimicking this definition with the discrete divergence. And now the twist in the discrete setting is that it's not completely canonical on how to do this division. Because here we have this vector field divided or evaluated at x, we're dividing it by the density at the same point. Here is a discrete version, a discrete vector field. So this is a quantity defined on the edges of my graph. But I would like to define it by the density, which is defined in the vertex. So there's something not completely canonical. So there's some room to play. And what we do is actually we put there something, maybe a function which I call capital lambda. And it depends on the density at x. And it involves also these transition rates of my Markov chain and the density at y. So it depends both on the density of x and density at y. And what is this function, lambda? Well, it's a suitable average between the two. And of course, there's room to play here. But sort of the most important one for the purpose of my talk is the case where lambda is the logarithmic mean, which is the following function. lambda rs equals the integral r to the minus alpha, st alpha. OK, so this is discrete transport metric, which was introduced in the independent diva Alex Bukin also for myself a problem years ago. OK, and why is this a natural object to study? Well, so if the main motivation comes from the fact that if you take this distance and you look at the gradient flow of the relative entropy with respect to the stationary measure of your Markov chain, then you get exactly the master equation for your Markov chain. So that's sort of the discrete JKL theorem. OK, so what is the topic of this talk? So the topic of this talk is actually if we can pass to the limit in suitable situations from this discrete metric to the content of each one. So sort of the relative entropy as a question, so question that we pass to the limit from the discrete particles. OK, so that's, of course, a natural thing to ask. Now, I should tell you something about what I mean by passing to the limit, because we were talking about the metric spaces in some sense, right? So we're looking at different metrics. So what I'm interested in is proving convergence of metric spaces and sort of the natural concept in this setting is the notion of quantum of convergence. Let me just recall one of the possible definitions. So consider a sequence of metric spaces. Xn dn xd metric spaces. Let's say they're compact. So then what's the possible definition of quantum of convergence? So this converges to x in the sense of quantum of starve. If the following holds, well, if there exist maps from the limiting space to the space xn, which are almost isometric and almost general. So if there exists fn from x to rn, and the sequence epsilon going to 0, such that the following holds, the distance between x and y minus the approximate distance between f and x, f and y is less than epsilon n, or x and y in x. And for all y in xn, x is in x in x. So the distance between f and x and y is less than epsilon n. OK, so this is a natural notion of convergence in this set. OK, so let me connect to this transport metric. So what is known in this direction? Well, there are actually two results that I would like to mention. So the first one is really sort of, I guess, the simplest thing that we tried to do. And this was done in a paper together with Nikolai G. He was 14, and what you did there is that we looked at this pre-tourist, so just the square letters in our D, with period boundary conditions. So the nv, so there are n sides in each direction. The dimension is d. Well, then you put as your generator of your Markov chain, you put the discrete of Lassian. Well, let me show this sort of that everything goes as it should go. So then the space of probability measures on the discrete torus endowed with this discrete transport metric just converts to the space of probability measures on the continuous torus, endowed with the Wasserstein 2 metric, as it should be. OK, so that was one result. And then there was another very nice paper by Niklas Trioz, 2017, from his PhD with the pigeon. And he did the following. So he also looked at the discrete torus, but at the continuous torus. And then what he does is he puts points in the torus, but not on the regular grid, but just at sort of more random locations. And the assumption is that they are sort of sufficiently uniformly distributed. So one typical example, which includes in a setting, is if you just sample uniformly at random, according to the uniform distribution on the torus. And points on the torus sufficiently uniform. And then what the next type was is then he constructs a graph in a natural way. Then for each point, he looks at all the other points, which are within the radius epsilon. And then he adds an edge to all the points within this distance of sine. So the second step is to construct a graph xn by connecting all points of distance epsilon depends on the number of points. OK, and then you have directly the setting of the Markov chain. If you take the generator of the random bulk on the graph, and you can ask the same question. So that was to resolve by three laws. So he showed that if this epsilon goes to 0, that's sufficiently slow. But that's sufficiently slow, and I'm not going to recall the complete technical condition. But in particular, it meant that epsilon divided by the typical distance, which is n to the minus 1 over d. So the typical distance to the next point. So this quantity should actually go to infinity. And then there are actually some additional assumptions. But under these assumptions, you prove the ground house of convergence. So if it goes to 0, sufficiently slow, this basically probabilities on this graph. And now, this discrete transport metric converges to the mass of the metric. And the torus. So it's a very nice result, in particular, because it does not have this rigid letter structure. But this is really sort of an arbitrary distributed collection of points. It is sufficiently uniform distributed. However, I should point out, actually, that these results are already completely disjoint. So this is not a special case of this. And that's due to the fact that this parameter epsilon is going to 0, but quite slowly. So what it means, in particular, is that if the number of points grows, then each of the points will actually be connected to more and more points. So the degree of the graph is actually growing. So first here, it will be constant. This is a little less. OK, so the question, I think, which arises naturally is what we looked at. It's actually, what happens now, if we consider actually sort of a more general discretization of the domain in Rn, more general than just this rectangular grid. But then, actually, where the number of neighbors remains constant. So more like a classical binotaur discretization. So would you expect that the efficiency by n to the minus 1 over d equals 0, for example, to a constant? If it's going to be true? Well, it's roughly corresponds to the setting that we are going to consider. OK. So I'll tell you a little bit. OK, so what is the setting that I would like to discuss today? So we have a convex domain. So this is the vector. And we have this. And let me sort of just consider a partition of this domain. Into sets which are, I don't know. So it is sets which are all polytopes, maybe, except for what we have to do at the boundary of the domain. So d is kp1 up to km. This partition of omega, it is sets with convex interior. OK, and then I need to make some assumptions. And I don't want, I mean, these are relatively standard so that you can find a volume literature. So one thing I'm going to assume is the following. So I'm going to assume that there are exist points, sequence of points indexed by the cells in my partition, such that the point xk belongs to cell k. And that's sort of the vector xk minus xl is perpendicular to the boundary between k and l. So in each cell there's a point like this. And what I want is that these line segments are perpendicular. Of course, that's a strong assumption, but it's, for instance, satisfied in the case of fornoid oscillations. And the k also mentioned this. So I think that's sort of the same kind of line. OK, and then we need some mild additional regularity conditions that I don't want to go into. OK, so then I need to define sort of the Markov chain associated to this. So I define transition rates. So the vertices of my graph are now sort of the cells in this partition. So I define transition rates between k and l. Well, I use this notation for the d minus 1 dimensional house-dark measure of the boundary divided by the volume of my cell times xk minus xl. OK, these rates are chosen. These are also quite standard. They are chosen in such a way actually that discrete heat equation converts to the continuous heat equation, which is just a classical result. So this is the assumptions. So the discrete heat flow converges. I could continue as well. So I can use these two different types of assumptions and sometimes the right rates to consider. OK, and then, well, in order to state my theorem, let me introduce one natural operator. So the pi t, also pi associated with this partition t, this is sort of the natural or canonical projection between probability measures on my domain omega to probability measures on the t, which just does the natural thing. So the mass that it assigns to the cell is just the mass plus the frame of the cell away. Absolutely. What do you do with the boundary mass? Yeah, OK, so that's a little bit tricky. So I take a partition. So actually, all these cells or each boundary mass is associated to one of the cells. I see. So I don't want to cut last twice. OK, let me now state the theorem, which shows that things are actually not as nice as we would have guessed. So here's the result. So I consider a sequence of admissible meshes. So in that sense, and then we can prove the following. So first of all, there is actually a boot upper bound for the discrete matrix. So for all probability measures in my domain, with every pair, we give this up as the size of my mesh goes to 0 of the transport distance between pi t0 and pi t1 is bounded from above by the master's term 2. So that's good. So there's a good upper bound for the discrete matrix. As a dot, it's bounded from above by the master's term matrix. OK, now the bad news is actually, or maybe the interesting thing is actually that the lower bound is actually not always true. So to prove the associated lower bounds, we need to make an additional assumption, which is very strong. So one sufficient condition is for us to the following. So if every pair of neighboring cells, what I do is I look at this quantity. So I look at the center of mass of the boundary between k and l. And I want the distance equal to the midpoint between xk and xl. So remember, so xk where these points in these cells. And so the condition is that the midpoint between those two points is exactly the center of mass of the cell. That's a very irrespective symmetry condition. And actually, I can read this a little bit. So I can add a small error term, but I cannot read it by much. But in particular, it works for regular masses. Well, it works for the regular grids, but not for the rectangular grids. I see. OK, so for the triangle, it's OK. But not for the rectangular. Yeah, exactly. So if not for the rectangular, unless you have a piece of paper. And actually, I'll show a count, for example, in one dimension for this. OK, so under this assumption, we have to know about this. So we have that again for all u, not a mu1, and here for omega, w2 mu1 is less than the limit of that quantity. pt0 mu1. And I'll read the remarks. So this is satisfied for this triangular and for the hexagonal grid, but maybe not for many other things. Why is it not satisfied for a rectangular grid? Well, if I have something like this. Yeah, I would, for instance, put something like this. But then here, I have to put it at this distance, right? I cannot put it here. Why not? I don't understand. Well, because the midpoint between these points should be the center of mass of this edge. Why wouldn't this break into the middle of the rectangles? I don't understand. Well, I think, so then, I mean, so these rectangles are not the same size, right? So this is smaller than this. It is. Oh, no, no, no. What about a regular rectangular? Oh, yeah, yeah. Regular rectangles fine. Yeah, exactly. Yes, so, okay, and so this is the result, and then sort of the remark is that this lower bound can fail even in one dimension. So if you're just consider one interval and you take this characterization of your interval into sort of non-economic intervals, not the same fact. How many minutes do I start? Three, four. Okay, so maybe I'll tell you a little bit. I'll tell you how the counter example works. So this is a counter example to the lower bounds in one dimension. So what we do is we look at the interval, so here's zero, here's one. We divide it into subintervals like this. So we take a longer interval followed by shorter intervals in an alternating way. So there are two parameters. So say that we have this one, two n cells. So the length of this interval is one minus r divided by n, and the length of this interval is r divided by n, of course, and the total number of r divided by zero is one. And now the claim is that if you fix r between zero and one, but not equal to one-half, so that these don't have the same length, and you want to transport a direct mass from here to here in a discrete setting, then actually your transport cost will not be one, as it should be, but it will be strictly less than one. So then we are putting the word system formula, so the transport cost between d-r at zero, which is projected at the discrete level, and d-r at one. And this will be found by some instance c, strictly less than one. So transporting a unit mass is cheaper than it should be. And how does it work? So how can you do this sort of this very cheap transport? Well, let me explain using a picture. The picture is a bit simplified, so let's suppose that we have a situation in which we have a long interval, a short one, followed by a long one, and we have some mass here in the long interval, times zero, and we want to transport at time one, you want all the mass over here. Now how can you do cheap transport? So what you do is that you take a small time epsilon, and in the small time interval epsilon, I take some of the mass from this interval, and I put it in a small interval. Something like this. So this is supposed to be slightly less than what it was here. So there's a lot of mass in this very narrow interval, and then what you're going to do is you're going to transport it in such a way that actually you keep the mass constant in this small interval, and you're going to move the mass from here to here. So this is a time one-half. So at time one minus epsilon, you get sort of this symmetric picture, right? So I say, okay, you get something like this. Maybe let me just finish my sentence. So now the thing is that actually the cost of transport is determined by the logarithmic mean of the densities. And because this interval is so narrow, the density is extremely high, and it's very little mass. And sort of the logarithmic mean of the density appears in the denominator of my transport cost. So if I have this logarithmic mean, which is very high, it means that my transport cost can be very low. So I can sort of cheat a little bit of the transport by putting a lot of mass in these very tiny intervals. That makes it a cheaper transport than what I actually shoot. Okay, so this shows the counter example, I think. So I'll give you a little bit of a break. If you had the arithmetic mean, your counter example would still work, right? Yeah, yeah, it's not the property of the logarithmic mean. So it's about the expressions you get at the beginning regarding the gradient flow. So you set the decimal options for the lambda, right? So no matter which option, you always have the result that the original Markov chain is the gradient flow? Well, I mean, so this logarithmic mean, you need to take, if you want your Markov chain to be the gradient flow of the logarithmic entropy. Okay. So if you want, you can also write your Markov chain as the gradient flow of another convex functional, and then you need to change this. Okay. You can also write like this grid-poor's gradient equation, and then you can write the gradient flow like you were placed in lower of the green by something. So what you're getting is you want to write the gradient flow with respect to the L2 distance? Of the outer distance. L2, L2, so instead of logarithmic. Well, I mean, then sort of, this will be just the h minus 1 gradient flow, right? Yes. So in that case, sort of, you take a function that's constant, which does not depend on the densities. I mean, this row is sort of the h minus 1 with respect to the row. And you want to write to be constant in that situation. I was wondering if your approach generalizes to transport of more general objects like temperatures and stuff. You mean this convergence results? Yeah. We haven't tried. We haven't tried. Thank you. Thanks for your question. Thank you. Thank you. Thank you. Thank you.
 It's a really great pleasure to be here.  OK, so I would like to present some joint work.  They're recent, so hopefully in the archive  in a couple of days.  And it's in collaboration with Peter Klaupach from Leitzig  and Eva Kopper from Hul.  So before stating the problem that we are studying,  maybe let me write down something that everybody knows here.  So that's the binomukul veneer problem for the system.  Let's take the system metric in Rn to Rn.  That's the formula expression.  So w2 square rho n times rho 1 is the minimum  of the kinetic energy which is needed to transport  between rho n and nopart.  So I integrate in time, integrate in space,  d dx divided by rho dx dx dt where rho and v satisfy  the continuity equation.  So dt v plus the divergence v is 0 with boundary conditions.  Not to the rho 1.  OK, so this is the binomukul veneer formula, which  is not the definition of Wasserstein,  but it's, of course, equivalent in the continuous setting.  What I'm interested in is this talk,  is sort of discrete analogs of this metric.  So they are not Wasserstein metric,  but they are defined in terms of an analog of this binomukul veneer.  So let me tell you about the discrete counterpart to this formula.  And to define it, I need to start with the generator  of a map of chain.  So let L be the generator of a reversible mark of chain  of a finite set x.  And so L has the following form.  So I have psi of x is the sum of y  of qxy times psi of y times psi of x.  For qxy are the transition rates of my mark of chain.  So these are the numerical numbers.  OK, so given such a generator of reversible mark of chain,  I can define the object that I'm interested in,  and that's the discrete transport metric  by an analog of the binomukul veneer formula.  So the mission for probability measures mu1 and mu0 to mu1 on x,  I define a distance w, it's a corny w,  square mu0 to mu1 as the epheymum following expression.  So again, I integrate in time.  And now the space integral will be this great sum,  and ptxy square divided by something dt.  And before I write something, I write the continuity equation.  So this is subject to dt mu dx plus discrete divergence  of v equal to 0.  So this would be 1 half sum over y dtxy minus v2 by x  equal to 0, which is the boundary condition mu times 0 and 1.  It's given by mu1.  OK, so as you see, I'm mimicking this definition  with the discrete divergence.  And now the twist in the discrete setting  is that it's not completely canonical  on how to do this division.  Because here we have this vector field divided or evaluated  at x, we're dividing it by the density at the same point.  Here is a discrete version, a discrete vector field.  So this is a quantity defined on the edges of my graph.  But I would like to define it by the density,  which is defined in the vertex.  So there's something not completely canonical.  So there's some room to play.  And what we do is actually we put there something, maybe  a function which I call capital lambda.  And it depends on the density at x.  And it involves also these transition rates  of my Markov chain and the density at y.  So it depends both on the density of x and density at y.  And what is this function, lambda?  Well, it's a suitable average between the two.  And of course, there's room to play here.  But sort of the most important one for the purpose of my talk  is the case where lambda is the logarithmic mean, which  is the following function.  lambda rs equals the integral r to the minus alpha, st alpha.  OK, so this is discrete transport metric,  which was introduced in the independent diva Alex Bukin  also for myself a problem years ago.  OK, and why is this a natural object to study?  Well, so if the main motivation comes from the fact  that if you take this distance and you  look at the gradient flow of the relative entropy  with respect to the stationary measure of your Markov chain,  then you get exactly the master equation for your Markov  chain.  So that's sort of the discrete JKL theorem.  OK, so what is the topic of this talk?  So the topic of this talk is actually  if we can pass to the limit in suitable situations  from this discrete metric to the content of each one.  So sort of the relative entropy as a question,  so question that we pass to the limit  from the discrete particles.  OK, so that's, of course, a natural thing to ask.  Now, I should tell you something about what I mean  by passing to the limit, because we  were talking about the metric spaces in some sense, right?  So we're looking at different metrics.  So what I'm interested in is proving  convergence of metric spaces and sort of the natural concept  in this setting is the notion of quantum of convergence.  Let me just recall one of the possible definitions.  So consider a sequence of metric spaces.  Xn dn xd metric spaces.  Let's say they're compact.  So then what's the possible definition  of quantum of convergence?  So this converges to x in the sense of quantum of starve.  If the following holds, well, if there  exist maps from the limiting space to the space xn, which  are almost isometric and almost general.  So if there exists fn from x to rn,  and the sequence epsilon going to 0,  such that the following holds, the distance between x  and y minus the approximate distance between f and x,  f and y is less than epsilon n, or x and y in x.  And for all y in xn, x is in x in x.  So the distance between f and x and y  is less than epsilon n.  OK, so this is a natural notion of convergence  in this set.  OK, so let me connect to this transport metric.  So what is known in this direction?  Well, there are actually two results  that I would like to mention.  So the first one is really sort of,  I guess, the simplest thing that we tried to do.  And this was done in a paper together with Nikolai G.  He was 14, and what you did there is that we looked at this  pre-tourist, so just the square letters in our D,  with period boundary conditions.  So the nv, so there are n sides in each direction.  The dimension is d.  Well, then you put as your generator of your Markov chain,  you put the discrete of Lassian.  Well, let me show this sort of that everything  goes as it should go.  So then the space of probability measures  on the discrete torus endowed with this discrete transport  metric just converts to the space of probability  measures on the continuous torus,  endowed with the Wasserstein 2 metric, as it should be.  OK, so that was one result.  And then there was another very nice paper  by Niklas Trioz, 2017, from his PhD with the pigeon.  And he did the following.  So he also looked at the discrete torus,  but at the continuous torus.  And then what he does is he puts points in the torus,  but not on the regular grid, but just  at sort of more random locations.  And the assumption is that they are sort of sufficiently  uniformly distributed.  So one typical example, which includes in a setting,  is if you just sample uniformly at random,  according to the uniform distribution on the torus.  And points on the torus sufficiently uniform.  And then what the next type was is then  he constructs a graph in a natural way.  Then for each point, he looks at all the other points, which  are within the radius epsilon.  And then he adds an edge to all the points  within this distance of sine.  So the second step is to construct a graph xn  by connecting all points of distance epsilon  depends on the number of points.  OK, and then you have directly the setting of the Markov  chain.  If you take the generator of the random bulk on the graph,  and you can ask the same question.  So that was to resolve by three laws.  So he showed that if this epsilon goes to 0,  that's sufficiently slow.  But that's sufficiently slow, and I'm not  going to recall the complete technical condition.  But in particular, it meant that epsilon  divided by the typical distance, which is n to the minus 1  over d.  So the typical distance to the next point.  So this quantity should actually go to infinity.  And then there are actually some additional assumptions.  But under these assumptions, you  prove the ground house of convergence.  So if it goes to 0, sufficiently slow,  this basically probabilities on this graph.  And now, this discrete transport metric converges  to the mass of the metric.  And the torus.  So it's a very nice result, in particular,  because it does not have this rigid letter structure.  But this is really sort of an arbitrary distributed  collection of points.  It is sufficiently uniform distributed.  However, I should point out, actually, that these results  are already completely disjoint.  So this is not a special case of this.  And that's due to the fact that this parameter epsilon  is going to 0, but quite slowly.  So what it means, in particular, is that if the number of points  grows, then each of the points will actually  be connected to more and more points.  So the degree of the graph is actually growing.  So first here, it will be constant.  This is a little less.  OK, so the question, I think, which arises naturally  is what we looked at.  It's actually, what happens now, if we consider actually  sort of a more general discretization of the domain  in Rn, more general than just this rectangular grid.  But then, actually, where the number of neighbors  remains constant.  So more like a classical binotaur discretization.  So would you expect that the efficiency by n to the minus 1  over d equals 0, for example, to a constant?  If it's going to be true?  Well, it's roughly corresponds to the setting  that we are going to consider.  OK.  So I'll tell you a little bit.  OK, so what is the setting that I would like to discuss today?  So we have a convex domain.  So this is the vector.  And we have this.  And let me sort of just consider a partition of this domain.  Into sets which are, I don't know.  So it is sets which are all polytopes, maybe,  except for what we have to do at the boundary of the domain.  So d is kp1 up to km.  This partition of omega, it is sets with convex interior.  OK, and then I need to make some assumptions.  And I don't want, I mean, these are relatively standard  so that you can find a volume literature.  So one thing I'm going to assume is the following.  So I'm going to assume that there are  exist points, sequence of points indexed by the cells in my partition,  such that the point xk belongs to cell k.  And that's sort of the vector xk minus xl is perpendicular  to the boundary between k and l.  So in each cell there's a point like this.  And what I want is that these line segments are perpendicular.  Of course, that's a strong assumption,  but it's, for instance, satisfied in the case of fornoid oscillations.  And the k also mentioned this.  So I think that's sort of the same kind of line.  OK, and then we need some mild additional regularity conditions  that I don't want to go into.  OK, so then I need to define sort of the Markov chain associated to this.  So I define transition rates.  So the vertices of my graph are now sort of the cells in this partition.  So I define transition rates between k and l.  Well, I use this notation for the d minus 1 dimensional  house-dark measure of the boundary divided by the volume of my cell  times xk minus xl.  OK, these rates are chosen.  These are also quite standard.  They are chosen in such a way actually that discrete heat equation  converts to the continuous heat equation,  which is just a classical result.  So this is the assumptions.  So the discrete heat flow converges.  I could continue as well.  So I can use these two different types of assumptions  and sometimes the right rates to consider.  OK, and then, well, in order to state my theorem,  let me introduce one natural operator.  So the pi t, also pi associated with this partition t,  this is sort of the natural or canonical projection  between probability measures on my domain omega  to probability measures on the t, which just  does the natural thing.  So the mass that it assigns to the cell  is just the mass plus the frame of the cell away.  Absolutely.  What do you do with the boundary mass?  Yeah, OK, so that's a little bit tricky.  So I take a partition.  So actually, all these cells or each boundary  mass is associated to one of the cells.  I see.  So I don't want to cut last twice.  OK, let me now state the theorem, which shows that things  are actually not as nice as we would have guessed.  So here's the result.  So I consider a sequence of admissible meshes.  So in that sense, and then we can prove the following.  So first of all, there is actually  a boot upper bound for the discrete matrix.  So for all probability measures in my domain,  with every pair, we give this up  as the size of my mesh goes to 0 of the transport distance  between pi t0 and pi t1 is bounded from above  by the master's term 2.  So that's good.  So there's a good upper bound for the discrete matrix.  As a dot, it's bounded from above by the master's term matrix.  OK, now the bad news is actually, or maybe the interesting thing  is actually that the lower bound is actually not always true.  So to prove the associated lower bounds,  we need to make an additional assumption, which is very strong.  So one sufficient condition is for us to the following.  So if every pair of neighboring cells, what I do  is I look at this quantity.  So I look at the center of mass of the boundary between k and l.  And I want the distance equal to the midpoint  between xk and xl.  So remember, so xk where these points in these cells.  And so the condition is that the midpoint between those two  points is exactly the center of mass of the cell.  That's a very irrespective symmetry condition.  And actually, I can read this a little bit.  So I can add a small error term, but I cannot read it by much.  But in particular, it works for regular masses.  Well, it works for the regular grids, but not for the rectangular grids.  I see.  OK, so for the triangle, it's OK.  But not for the rectangular.  Yeah, exactly.  So if not for the rectangular, unless you have a piece of paper.  And actually, I'll show a count, for example, in one dimension for this.  OK, so under this assumption, we have to know about this.  So we have that again for all u, not a mu1,  and here for omega, w2 mu1 is less than the limit of that quantity.  pt0 mu1.  And I'll read the remarks.  So this is satisfied for this triangular and for the hexagonal grid,  but maybe not for many other things.  Why is it not satisfied for a rectangular grid?  Well, if I have something like this.  Yeah, I would, for instance, put something like this.  But then here, I have to put it at this distance, right?  I cannot put it here.  Why not?  I don't understand.  Well, because the midpoint between these points should be the center of mass of this edge.  Why wouldn't this break into the middle of the rectangles?  I don't understand.  Well, I think, so then, I mean, so these rectangles are not the same size, right?  So this is smaller than this.  It is.  Oh, no, no, no.  What about a regular rectangular?  Oh, yeah, yeah.  Regular rectangles fine.  Yeah, exactly.  Yes, so, okay, and so this is the result, and then sort of the remark is that this lower bound  can fail even in one dimension.  So if you're just consider one interval and you take this characterization of your interval  into sort of non-economic intervals, not the same fact.  How many minutes do I start?  Three, four.  Okay, so maybe I'll tell you a little bit.  I'll tell you how the counter example works.  So this is a counter example to the lower bounds in one dimension.  So what we do is we look at the interval, so here's zero, here's one.  We divide it into subintervals like this.  So we take a longer interval followed by shorter intervals in an alternating way.  So there are two parameters.  So say that we have this one, two n cells.  So the length of this interval is one minus r divided by n, and the length of this interval  is r divided by n, of course, and the total number of r divided by zero is one.  And now the claim is that if you fix r between zero and one, but not equal to one-half,  so that these don't have the same length,  and you want to transport a direct mass from here to here in a discrete setting,  then actually your transport cost will not be one, as it should be, but it will be strictly less than one.  So then we are putting the word system formula, so the transport cost between d-r at zero,  which is projected at the discrete level, and d-r at one.  And this will be found by some instance c, strictly less than one.  So transporting a unit mass is cheaper than it should be.  And how does it work?  So how can you do this sort of this very cheap transport?  Well, let me explain using a picture.  The picture is a bit simplified, so let's suppose that we have a situation  in which we have a long interval, a short one, followed by a long one,  and we have some mass here in the long interval, times zero,  and we want to transport at time one, you want all the mass over here.  Now how can you do cheap transport?  So what you do is that you take a small time epsilon,  and in the small time interval epsilon, I take some of the mass from this interval,  and I put it in a small interval.  Something like this.  So this is supposed to be slightly less than what it was here.  So there's a lot of mass in this very narrow interval,  and then what you're going to do is you're going to transport it in such a way  that actually you keep the mass constant in this small interval,  and you're going to move the mass from here to here.  So this is a time one-half.  So at time one minus epsilon, you get sort of this symmetric picture, right?  So I say, okay, you get something like this.  Maybe let me just finish my sentence.  So now the thing is that actually the cost of transport is determined  by the logarithmic mean of the densities.  And because this interval is so narrow, the density is extremely high,  and it's very little mass.  And sort of the logarithmic mean of the density  appears in the denominator of my transport cost.  So if I have this logarithmic mean, which is very high,  it means that my transport cost can be very low.  So I can sort of cheat a little bit of the transport  by putting a lot of mass in these very tiny intervals.  That makes it a cheaper transport than what I actually shoot.  Okay, so this shows the counter example, I think.  So I'll give you a little bit of a break.  If you had the arithmetic mean, your counter example would still work, right?  Yeah, yeah, it's not the property of the logarithmic mean.  So it's about the expressions you get at the beginning regarding the gradient flow.  So you set the decimal options for the lambda, right?  So no matter which option, you always have the result  that the original Markov chain is the gradient flow?  Well, I mean, so this logarithmic mean, you need to take,  if you want your Markov chain to be the gradient flow of the logarithmic entropy.  Okay.  So if you want, you can also write your Markov chain  as the gradient flow of another convex functional,  and then you need to change this.  Okay.  You can also write like this grid-poor's gradient equation,  and then you can write the gradient flow like you were placed in lower of the green by something.  So what you're getting is you want to write the gradient flow with respect to the L2 distance?  Of the outer distance.  L2, L2, so instead of logarithmic.  Well, I mean, then sort of, this will be just the h minus 1 gradient flow, right?  Yes.  So in that case, sort of, you take a function that's constant,  which does not depend on the densities.  I mean, this row is sort of the h minus 1 with respect to the row.  And you want to write to be constant in that situation.  I was wondering if your approach generalizes to transport of more general objects like temperatures and stuff.  You mean this convergence results?  Yeah.  We haven't tried.  We haven't tried.  Thank you.  Thanks for your question.  Thank you.  Thank you.  Thank you.  Thank you.
201804121033-Maas_lrv_0_671.png 201804121033-Maas_lrv_672_911.png 201804121033-Maas_lrv_912_1583.png 201804121033-Maas_lrv_1584_3347.png 201804121033-Maas_lrv_3348_6083.png 201804121033-Maas_lrv_6084_7391.png 201804121033-Maas_lrv_7392_7811.png 201804121033-Maas_lrv_7812_8363.png 201804121033-Maas_lrv_8364_9683.png 201804121033-Maas_lrv_9684_11903.png 201804121033-Maas_lrv_11904_12107.png 201804121033-Maas_lrv_12108_14255.png 201804121033-Maas_lrv_14256_14459.png 201804121033-Maas_lrv_14460_19283.png 201804121033-Maas_lrv_19284_24707.png 201804121033-Maas_lrv_24708_28307.png 201804121033-Maas_lrv_28308_32183.png 201804121033-Maas_lrv_32184_32627.png 201804121033-Maas_lrv_32628_33683.png 201804121033-Maas_lrv_33684_36023.png 201804121033-Maas_lrv_36024_36167.png 201804121033-Maas_lrv_36168_45155.png 201804121033-Maas_lrv_45156_48683.png 201804121033-Maas_lrv_48684_49679.png 201804121033-Maas_lrv_49680_49751.png 201804121033-Maas_lrv_49752_50256.png
It's a really great pleasure to be here. OK, so I would like to present some joint work. They're recent, so hopefully in the archive in a couple of days. And it's in collaboration with Peter Klaupach from Leitzig and Eva Kopper from Hul. So before stating the problem that we are studying, maybe let me write down something that everybody knows here. So that's the binomukul veneer problem for the system. Let's take the system metric in Rn to Rn. That's the formula expression. So w2 square rho n times rho 1 is the minimum of the kinetic energy which is needed to transport between rho n and nopart. So I integrate in time, integrate in space, d dx divided by rho dx dx dt where rho and v satisfy the continuity equation. So dt v plus the divergence v is 0 with boundary conditions. Not to the rho 1. OK, so this is the binomukul veneer formula, which is not the definition of Wasserstein, but it's, of course, equivalent in the continuous setting. What I'm interested in is this talk, is sort of discrete analogs of this metric. So they are not Wasserstein metric, but they are defined in terms of an analog of this binomukul veneer. So let me tell you about the discrete counterpart to this formula. And to define it, I need to start with the generator of a map of chain. So let L be the generator of a reversible mark of chain of a finite set x. And so L has the following form. So I have psi of x is the sum of y of qxy times psi of y times psi of x. For qxy are the transition rates of my mark of chain. So these are the numerical numbers. OK, so given such a generator of reversible mark of chain, I can define the object that I'm interested in, and that's the discrete transport metric by an analog of the binomukul veneer formula. So the mission for probability measures mu1 and mu0 to mu1 on x, I define a distance w, it's a corny w, square mu0 to mu1 as the epheymum following expression. So again, I integrate in time. And now the space integral will be this great sum, and ptxy square divided by something dt. And before I write something, I write the continuity equation. So this is subject to dt mu dx plus discrete divergence of v equal to 0. So this would be 1 half sum over y dtxy minus v2 by x equal to 0, which is the boundary condition mu times 0 and 1. It's given by mu1. OK, so as you see, I'm mimicking this definition with the discrete divergence. And now the twist in the discrete setting is that it's not completely canonical on how to do this division. Because here we have this vector field divided or evaluated at x, we're dividing it by the density at the same point. Here is a discrete version, a discrete vector field. So this is a quantity defined on the edges of my graph. But I would like to define it by the density, which is defined in the vertex. So there's something not completely canonical. So there's some room to play. And what we do is actually we put there something, maybe a function which I call capital lambda. And it depends on the density at x. And it involves also these transition rates of my Markov chain and the density at y. So it depends both on the density of x and density at y. And what is this function, lambda? Well, it's a suitable average between the two. And of course, there's room to play here. But sort of the most important one for the purpose of my talk is the case where lambda is the logarithmic mean, which is the following function. lambda rs equals the integral r to the minus alpha, st alpha. OK, so this is discrete transport metric, which was introduced in the independent diva Alex Bukin also for myself a problem years ago. OK, and why is this a natural object to study? Well, so if the main motivation comes from the fact that if you take this distance and you look at the gradient flow of the relative entropy with respect to the stationary measure of your Markov chain, then you get exactly the master equation for your Markov chain. So that's sort of the discrete JKL theorem. OK, so what is the topic of this talk? So the topic of this talk is actually if we can pass to the limit in suitable situations from this discrete metric to the content of each one. So sort of the relative entropy as a question, so question that we pass to the limit from the discrete particles. OK, so that's, of course, a natural thing to ask. Now, I should tell you something about what I mean by passing to the limit, because we were talking about the metric spaces in some sense, right? So we're looking at different metrics. So what I'm interested in is proving convergence of metric spaces and sort of the natural concept in this setting is the notion of quantum of convergence. Let me just recall one of the possible definitions. So consider a sequence of metric spaces. Xn dn xd metric spaces. Let's say they're compact. So then what's the possible definition of quantum of convergence? So this converges to x in the sense of quantum of starve. If the following holds, well, if there exist maps from the limiting space to the space xn, which are almost isometric and almost general. So if there exists fn from x to rn, and the sequence epsilon going to 0, such that the following holds, the distance between x and y minus the approximate distance between f and x, f and y is less than epsilon n, or x and y in x. And for all y in xn, x is in x in x. So the distance between f and x and y is less than epsilon n. OK, so this is a natural notion of convergence in this set. OK, so let me connect to this transport metric. So what is known in this direction? Well, there are actually two results that I would like to mention. So the first one is really sort of, I guess, the simplest thing that we tried to do. And this was done in a paper together with Nikolai G. He was 14, and what you did there is that we looked at this pre-tourist, so just the square letters in our D, with period boundary conditions. So the nv, so there are n sides in each direction. The dimension is d. Well, then you put as your generator of your Markov chain, you put the discrete of Lassian. Well, let me show this sort of that everything goes as it should go. So then the space of probability measures on the discrete torus endowed with this discrete transport metric just converts to the space of probability measures on the continuous torus, endowed with the Wasserstein 2 metric, as it should be. OK, so that was one result. And then there was another very nice paper by Niklas Trioz, 2017, from his PhD with the pigeon. And he did the following. So he also looked at the discrete torus, but at the continuous torus. And then what he does is he puts points in the torus, but not on the regular grid, but just at sort of more random locations. And the assumption is that they are sort of sufficiently uniformly distributed. So one typical example, which includes in a setting, is if you just sample uniformly at random, according to the uniform distribution on the torus. And points on the torus sufficiently uniform. And then what the next type was is then he constructs a graph in a natural way. Then for each point, he looks at all the other points, which are within the radius epsilon. And then he adds an edge to all the points within this distance of sine. So the second step is to construct a graph xn by connecting all points of distance epsilon depends on the number of points. OK, and then you have directly the setting of the Markov chain. If you take the generator of the random bulk on the graph, and you can ask the same question. So that was to resolve by three laws. So he showed that if this epsilon goes to 0, that's sufficiently slow. But that's sufficiently slow, and I'm not going to recall the complete technical condition. But in particular, it meant that epsilon divided by the typical distance, which is n to the minus 1 over d. So the typical distance to the next point. So this quantity should actually go to infinity. And then there are actually some additional assumptions. But under these assumptions, you prove the ground house of convergence. So if it goes to 0, sufficiently slow, this basically probabilities on this graph. And now, this discrete transport metric converges to the mass of the metric. And the torus. So it's a very nice result, in particular, because it does not have this rigid letter structure. But this is really sort of an arbitrary distributed collection of points. It is sufficiently uniform distributed. However, I should point out, actually, that these results are already completely disjoint. So this is not a special case of this. And that's due to the fact that this parameter epsilon is going to 0, but quite slowly. So what it means, in particular, is that if the number of points grows, then each of the points will actually be connected to more and more points. So the degree of the graph is actually growing. So first here, it will be constant. This is a little less. OK, so the question, I think, which arises naturally is what we looked at. It's actually, what happens now, if we consider actually sort of a more general discretization of the domain in Rn, more general than just this rectangular grid. But then, actually, where the number of neighbors remains constant. So more like a classical binotaur discretization. So would you expect that the efficiency by n to the minus 1 over d equals 0, for example, to a constant? If it's going to be true? Well, it's roughly corresponds to the setting that we are going to consider. OK. So I'll tell you a little bit. OK, so what is the setting that I would like to discuss today? So we have a convex domain. So this is the vector. And we have this. And let me sort of just consider a partition of this domain. Into sets which are, I don't know. So it is sets which are all polytopes, maybe, except for what we have to do at the boundary of the domain. So d is kp1 up to km. This partition of omega, it is sets with convex interior. OK, and then I need to make some assumptions. And I don't want, I mean, these are relatively standard so that you can find a volume literature. So one thing I'm going to assume is the following. So I'm going to assume that there are exist points, sequence of points indexed by the cells in my partition, such that the point xk belongs to cell k. And that's sort of the vector xk minus xl is perpendicular to the boundary between k and l. So in each cell there's a point like this. And what I want is that these line segments are perpendicular. Of course, that's a strong assumption, but it's, for instance, satisfied in the case of fornoid oscillations. And the k also mentioned this. So I think that's sort of the same kind of line. OK, and then we need some mild additional regularity conditions that I don't want to go into. OK, so then I need to define sort of the Markov chain associated to this. So I define transition rates. So the vertices of my graph are now sort of the cells in this partition. So I define transition rates between k and l. Well, I use this notation for the d minus 1 dimensional house-dark measure of the boundary divided by the volume of my cell times xk minus xl. OK, these rates are chosen. These are also quite standard. They are chosen in such a way actually that discrete heat equation converts to the continuous heat equation, which is just a classical result. So this is the assumptions. So the discrete heat flow converges. I could continue as well. So I can use these two different types of assumptions and sometimes the right rates to consider. OK, and then, well, in order to state my theorem, let me introduce one natural operator. So the pi t, also pi associated with this partition t, this is sort of the natural or canonical projection between probability measures on my domain omega to probability measures on the t, which just does the natural thing. So the mass that it assigns to the cell is just the mass plus the frame of the cell away. Absolutely. What do you do with the boundary mass? Yeah, OK, so that's a little bit tricky. So I take a partition. So actually, all these cells or each boundary mass is associated to one of the cells. I see. So I don't want to cut last twice. OK, let me now state the theorem, which shows that things are actually not as nice as we would have guessed. So here's the result. So I consider a sequence of admissible meshes. So in that sense, and then we can prove the following. So first of all, there is actually a boot upper bound for the discrete matrix. So for all probability measures in my domain, with every pair, we give this up as the size of my mesh goes to 0 of the transport distance between pi t0 and pi t1 is bounded from above by the master's term 2. So that's good. So there's a good upper bound for the discrete matrix. As a dot, it's bounded from above by the master's term matrix. OK, now the bad news is actually, or maybe the interesting thing is actually that the lower bound is actually not always true. So to prove the associated lower bounds, we need to make an additional assumption, which is very strong. So one sufficient condition is for us to the following. So if every pair of neighboring cells, what I do is I look at this quantity. So I look at the center of mass of the boundary between k and l. And I want the distance equal to the midpoint between xk and xl. So remember, so xk where these points in these cells. And so the condition is that the midpoint between those two points is exactly the center of mass of the cell. That's a very irrespective symmetry condition. And actually, I can read this a little bit. So I can add a small error term, but I cannot read it by much. But in particular, it works for regular masses. Well, it works for the regular grids, but not for the rectangular grids. I see. OK, so for the triangle, it's OK. But not for the rectangular. Yeah, exactly. So if not for the rectangular, unless you have a piece of paper. And actually, I'll show a count, for example, in one dimension for this. OK, so under this assumption, we have to know about this. So we have that again for all u, not a mu1, and here for omega, w2 mu1 is less than the limit of that quantity. pt0 mu1. And I'll read the remarks. So this is satisfied for this triangular and for the hexagonal grid, but maybe not for many other things. Why is it not satisfied for a rectangular grid? Well, if I have something like this. Yeah, I would, for instance, put something like this. But then here, I have to put it at this distance, right? I cannot put it here. Why not? I don't understand. Well, because the midpoint between these points should be the center of mass of this edge. Why wouldn't this break into the middle of the rectangles? I don't understand. Well, I think, so then, I mean, so these rectangles are not the same size, right? So this is smaller than this. It is. Oh, no, no, no. What about a regular rectangular? Oh, yeah, yeah. Regular rectangles fine. Yeah, exactly. Yes, so, okay, and so this is the result, and then sort of the remark is that this lower bound can fail even in one dimension. So if you're just consider one interval and you take this characterization of your interval into sort of non-economic intervals, not the same fact. How many minutes do I start? Three, four. Okay, so maybe I'll tell you a little bit. I'll tell you how the counter example works. So this is a counter example to the lower bounds in one dimension. So what we do is we look at the interval, so here's zero, here's one. We divide it into subintervals like this. So we take a longer interval followed by shorter intervals in an alternating way. So there are two parameters. So say that we have this one, two n cells. So the length of this interval is one minus r divided by n, and the length of this interval is r divided by n, of course, and the total number of r divided by zero is one. And now the claim is that if you fix r between zero and one, but not equal to one-half, so that these don't have the same length, and you want to transport a direct mass from here to here in a discrete setting, then actually your transport cost will not be one, as it should be, but it will be strictly less than one. So then we are putting the word system formula, so the transport cost between d-r at zero, which is projected at the discrete level, and d-r at one. And this will be found by some instance c, strictly less than one. So transporting a unit mass is cheaper than it should be. And how does it work? So how can you do this sort of this very cheap transport? Well, let me explain using a picture. The picture is a bit simplified, so let's suppose that we have a situation in which we have a long interval, a short one, followed by a long one, and we have some mass here in the long interval, times zero, and we want to transport at time one, you want all the mass over here. Now how can you do cheap transport? So what you do is that you take a small time epsilon, and in the small time interval epsilon, I take some of the mass from this interval, and I put it in a small interval. Something like this. So this is supposed to be slightly less than what it was here. So there's a lot of mass in this very narrow interval, and then what you're going to do is you're going to transport it in such a way that actually you keep the mass constant in this small interval, and you're going to move the mass from here to here. So this is a time one-half. So at time one minus epsilon, you get sort of this symmetric picture, right? So I say, okay, you get something like this. Maybe let me just finish my sentence. So now the thing is that actually the cost of transport is determined by the logarithmic mean of the densities. And because this interval is so narrow, the density is extremely high, and it's very little mass. And sort of the logarithmic mean of the density appears in the denominator of my transport cost. So if I have this logarithmic mean, which is very high, it means that my transport cost can be very low. So I can sort of cheat a little bit of the transport by putting a lot of mass in these very tiny intervals. That makes it a cheaper transport than what I actually shoot. Okay, so this shows the counter example, I think. So I'll give you a little bit of a break. If you had the arithmetic mean, your counter example would still work, right? Yeah, yeah, it's not the property of the logarithmic mean. So it's about the expressions you get at the beginning regarding the gradient flow. So you set the decimal options for the lambda, right? So no matter which option, you always have the result that the original Markov chain is the gradient flow? Well, I mean, so this logarithmic mean, you need to take, if you want your Markov chain to be the gradient flow of the logarithmic entropy. Okay. So if you want, you can also write your Markov chain as the gradient flow of another convex functional, and then you need to change this. Okay. You can also write like this grid-poor's gradient equation, and then you can write the gradient flow like you were placed in lower of the green by something. So what you're getting is you want to write the gradient flow with respect to the L2 distance? Of the outer distance. L2, L2, so instead of logarithmic. Well, I mean, then sort of, this will be just the h minus 1 gradient flow, right? Yes. So in that case, sort of, you take a function that's constant, which does not depend on the densities. I mean, this row is sort of the h minus 1 with respect to the row. And you want to write to be constant in that situation. I was wondering if your approach generalizes to transport of more general objects like temperatures and stuff. You mean this convergence results? Yeah. We haven't tried. We haven't tried. Thank you. Thanks for your question. Thank you. Thank you. Thank you. Thank you.
of days. And it's in collaboration with Peter formula. So the mission for probability measures discrete transport metric just converts to the space of probability measures on the continuous we consider actually sort of a more general discretization of the domain in Rn, more general have a convex domain. So this is the vector. And assumptions. So the discrete heat flow converges. interesting thing is actually that the lower the associated lower bounds, we need to make an That's a very irrespective symmetry condition.