Semi-discrete unbalanced optimal transport and quantization
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Schmitzer, Bernhard
"Semi-discrete optimal transport between a discrete source and a continuous target has intriguing geometric properties and applications in modelling and numerical methods. Unbalanced transport, which allows the comparison of measures with unequal mass, has recently been studied in great detail by various authors. In this talk we consider the combination of both concepts. The tessellation structure of semi-discrete transport survives and there is an interplay between the length scales of the discrete source and unbalanced transport which leads to qualitatively new regimes in the crystallization limit."
 That's the setting. And then, of course, you all know that in the case that x length space, then also the resulting Wasserstein space will be a length space. That means there will be shortest path, which correspond to the so-called displacement interpolation. So instead of just doing the linear interpolation between two measures, we're actually moving mass in the base space. And then we can associate a momentum field with this, or a velocity field. And it turns out you can actually rewrite the whole transport problem in terms of these fields of the mass and the momentum field, satisfying the continuity equation in a weak sense. And then you minimize this action, which is essentially the kinetic energy integrated in toy. Yeah, and if you set p equal to 2, this looks a lot like Ray-Banian-Baniforce. I'm just doing this because I will briefly want to talk about unbalance optimal transport, because I don't think everyone's familiar with this. So this is the motivation. Let's see. We have a problem like that. We have two bunches of mass here in the beginning and two different batches of mass in the end. We want to interpolate. And if they're not equally split up, then there will be no choice but to transport a bit of mass from one to the other one. And if this is just a tiny measurement error, and this is very far apart, then this is a very unnatural behavior. You want to get rid of this. Well, things actually maybe have to grow or shrink. If we want to model this, we want a behavior like that. Well, one way to do this is starting from this Ben-Aubigny formula, just modified to make it unbalanced. So we add a source term, theta, here, which appears here in the continuity equation. And then we have to modify our action to penalize the theta as well. So we remove the kinetic energy and we add something which contains theta. And the idea is not that new. And in fact, a lot of different things for phi have been tried, more like TV-type things for theta, L1-type, or combined L1 and L2 things. And the thing I want to focus on today is this particular term, which we call the vasestant-discharal distance. And other people came up with it as well. For instance, Euromucan-Savare called it the Helio-Konturvitsch distance. And what you can see here is, essentially, we have here the optimal transport part. And here we add a term which looks like the remaining tensor of the visceral distance. So this is the Riemannian tensor of vasestant. This is the Riemannian tensor of visceral. We just combine it. Gives it a bit more options to handle solutions here. OK. Now, the good news is this new object indeed does yield the geodesic distance on non-negative measures. And just to see a bit more what it does, what it structures, we looked at geodesic between direct measures. So we started with the direct x0, mass 0, when I go to x1, m1. And then the standard vasestant measurement would happen is, if both m's are equal, then the geodesic is a Dirac moving at constant speed from the initial to the final location. Now, in the Fischer-Rauke case, in the Vasestant-Diescher-Rauke case, if the two Diracs are sufficiently close, closer than pi in this case, then the geodesic will also be a traveling Dirac, but it will reduce its mass bit in the middle to save on transport values. So in the beginning, it will reduce the mass, then transport is cheaper, and then you have to grow the mass back. And finally, when the masses are too far apart, it turns out that transport is no longer economical, and you do everything via the Fischer-Rauke term. So the first Dirac is simply being teleported, if you want, to a second Dirac. And now, this is already a nice result, I think. Diracs are staying Diracs. They're not being destroyed or smeared out. But the most, I think, most pleasant result is that, in fact, general geodesics can be decomposed into geodesics between Diracs. So we kind of understand very nicely what this distance is doing. And here's a small numerical example. So we have a density that we interpolate into another density. If you just take the L2 or TV or whatever interpolation, you just get this fading, not very satisfying. If you do Rathenstein 2, you get, well, you get movement of mass, right? No more fading. But here, for instance, you have this chunk of mass that's traveling from the whole image from this square to form this Q down there. And this may be unpleasant. This may be an artifact that you want to get rid of, and in the unbalanced case, you get it. Locally, you get nice interpolations, but globally, there is no interaction between them. So I think this has its merits in many applications. OK. Now, another way to tackle the unbalanced transport question is to start from the Kantorovitch formulation. So we started from Benjamin Bernier. You could also start from Kantorovitch, and you relaxed the marginal constraints. So now you're optimizing over arbitrary, not negative measures. You pay the transport price. And here, you penalize the deviation of the first marginal from mu and the second marginal from mu by some marginal discrepancy function, which usually has some form, some integral of some small f. And there's more choices, but today we only need this one, where f is super linear, so it's going to be infinite if it's not absolutely continuous with respect to the marginal. And then you can try to solve this. You can go to the dual problem. It looks very similar than before. We have the same feasible set and the same constraints. But now, it's no longer just the overlap of alpha with mu, but now there's this minus f star minus. And this is, in general, an increasing concave function. So this is still a convex optimization problem, concave maximization problem. All right. And you can recover the balanced case very easily by setting f to be the indicator function of 1. Then here, rho has no choice but to be equal to mu. Otherwise, this will be infinity. And then if you do this conjugation, you will get that this function is indeed the identity. So these terms simply disappear when you have the original dual problem. And now, the most elegant or beautiful result of all this that actually there's a bridge between those two approaches. You can recover this, but then, for our handling of the distance by setting this marginal is pregnancy to the kubat-Liber divergence. And the cost factor of this particular cost function. You don't need to worry about the details. This is just some function. But this is a radial cost. This is an increasing function of the distance. And it will be infinity after, oh, I didn't adapt the normalizations after pi half. So this is a slightly different trade between transport and mass change. So there will be no transport further than this. Beyond the system, everything has to be handled by kubat-Liber. OK. Then the final thing that we need, the final ingredient, before we can put everything together, is semi-discreet transport. So now mu will be an absolute continuous measure. And mu will be a discrete measure of some Dirac's with mass mi at locations xi. Then we can almost immediately tell that the form of the optimal coupling has to be something like this. So we chop up mu into cells ci. And then everything in the cell ci is being transported to xi. This has to be the form of the optimal coupling. And these cells ci that are the so-called generalized like air cells. So for a weight vector w, we just check where is it. This thing is maximal. And all the points x, where this is maximal, they are in cell ci. So this is related to the C transport. Of course, you will know this is optimal transport. And in our case, since the cost may be infinite, there may be a residual set where we cannot go with finite cost. And this will be treated separately occasionally. OK. If you haven't seen those guys, just think of this as the generalization of the Voronoi cells. If you just pick c to the distance and you set this weight vector to 0, this is just the Voronoi cells. But you see, if I turn up certain w, I can make this smaller. And so I will increase the corresponding cell. You can do a bit of competition between the different cells. And then starting from this, you can go back to the original transport problem. And you will get that in the semi-discrete case, you can solve optimal transport with this tessellation formulation, where this is essentially, you can get from the dual to this very quickly. So our dual measure nu, sorry, only lives on these points xi. So we only need the dual variable beta at these points. So this will be the dual variable beta only at those locations. So this is the original dual term. And then we just pick the optimal alpha for a fixed beta. We make alpha as large as possible. It has to be smaller than all the dual constraints. And this is the dual constraint that will be active on this particular cell. So this is a very simple transformation. And you will get to this particular formulation. And in fact, this is also the base point for very efficient numerical methods. That contact, for instance, is working on. You want to get that by Bruno Levy? OK, I think now we have all the ingredients assembled. Now we can combine them. So the first good news is this dual tessellation formulation survives. Now the optimal coupling is a slightly more general form. We still chop up some measure and transport everything in the corresponding cell to the corresponding point. But now this measure that we chop up is no longer necessarily equal to mu, but it can be something else due to the marginal discrepancy. Then if you look at the dual formulation, you can do the same trick. We introduce this new effective dual variable w. And then we just pick the corresponding alpha as large as possible, which we result in this guy. And instead of just being the overlap between the two, we have this minus f star minus appearing both in the alpha and in the beta term. And then there's the residual term, things that cannot be reached. We have no choice but to remove this mass. We have to pay f zero for this. So the balanced case, this would be a problem, because then this is infinity. But in the unbalanced case, this might still be OK. So this is the dual tessellation formulation. It survives almost unchanged. And now in this case, again, we recover the balanced case. It's very easy. But now we can also do a primal version of this. So we take these kinds of couplings, and we don't know the rho yet, and we don't know the w yet. We can just plug it into the primal one and optimize over those two guys. We optimize over omega s. And w, and we're probably going to optimize over rho. And there cannot be any mass in the residual. And then you get this is the transport term for every cell to transport to the cross-point. This is the first marginal discrepancy. This is the second marginal discrepancy. It's very natural. And this doesn't really make sense in the balanced case, because it would only be finite when it's optimal. Because this is only finite when the second marginal constraint is satisfied. This is only finite when the first marginal constraint is satisfied, and then you know they're already optimal. So it doesn't really make sense in the balanced case, in the unbalanced case. I think it's natural to write this thing down. OK, let's go further. Let's try a few things. Now we have choices to make. We have cost function, and we have this marginal discrepancy to choose. So we can get very different behavior. So let's start with the standard Wasserstein 2 case to practice. We just take the square distance, and we take this f to be the indicator function of 1, which means that calligraphic f can only be the indicator function of mu. So the marginal is actually fixed. Then these cell CI will be actually the weighted Laguerre cells with piecewise straight lines. And there will be no residual, and the marginal rho has no choice but to be equal to mu. So this is the back measure that I'm currently just using as the first marginal. And now in the Wasserstein 2 case, it's just chopped up into these cells, and every cell is transported onto this point. So now let's start unbalanced. Now we change f to be the calligraphic letter divergence. Now the first marginal is free. And what happens is the cells are still weighted like air cells. They're slightly different, but the shape is the same, essentially. And now the first marginal is free, and you see that it's a bit as higher density when you close the points, because then it's cheaper to transport. And the density is decreased if you're far from the point, because you don't want to transport as much. So that's very natural. And in this particular case, you will notice that the support of this new free measure rho is now still the whole space, because this calligraphic letter divergence is essentially minus infinite slope at 0. So even if you're very far, and it's very expensive to transport, it's still cheaper to transport a very little bit to gain a bit of this infinite slope. So this measure still has infinite support. Full support. Now we go to this Wasserstein Fisher-Rauw case. So we keep the calligraphic letter divergence, and we change the cost to this particular one, which is infinite after the pi half. Now what we get is, for the first time, we have a non-empty residual set. This is marked here in white. These points, we cannot transport them to any of the red points with the finite cost. We have no choice but to send rho to 0 here. Otherwise, it would be infinite. But everywhere else, for the same argument as before, everywhere else rho has support. And finally, we tried quadratic regularization. We just take, again, the standard Euclidean distance. And now we penalize in a quadratic fashion the deviation from the original marginal. Then the residual set is now a non-empty because the cost is finite. So everything here is not white. But still, the measure rho does not have full support. Because here, it's a finite cost to transport to there, but it's even cheaper to just neglect the mass completely. So we have qualitatively very different behavior here. Just the standard balance case. There's not enough degrees of freedom. Now here, it's almost the same just the measure rho is varying a bit. Now here, we have only bounded support. And that's due to the infinite transport cost. And here, we have bounded support. But that is now due to the finite throwing mass away cost. We have four qualitatively very different behaviors. That's a nice suit to play with. OK. And we also see that there's kind of a length scale intrinsically involved in all of this. The length scale between those, the distance of these points and how far we can transport. So now let's play with this length scale. And for this, we look now at the scale of cost. See epsilon, we just put an epsilon here. So if my epsilon is very small, it will look like our space is very large. And transport will become very expensive. And for simplicity, we just assume that f of 1 is equal to 0. That means if possible, we prefer to balance the masses. And we pay for not balancing them. OK. Now this is the problem that we try to solve. If we have epsilon go to infinity, then we can see here that this is becoming very small. And transport is becoming very cheap. We're making the space very small. So we don't really need to change the map. We can transport everything with very little cost. And it will go to 0, essentially. If we let epsilon go to 0, then transport will become prohibitively expensive. And we have to do everything via the marginal constraints. And here is what we can see. For large epsilon, in this case, large means 1. This is the back measure. It's transported onto those four points. And you don't see anything. This is constant. Now if you make epsilon smaller and smaller, transport is becoming more expensive. And what you can see here in the cells, the standard, they're no longer the generalized like air cells, but now they're becoming curved. And now you can see here, you can see the residual popping up. So now the unbalanced effects show up if you make epsilon smaller and smaller. And also you can see here in the free marginal row, in the beginning it's essentially equal to the back measure. And you can start to see this emphasis near the points where you can actually transport to. So this is very natural. And here's the same example with a bit more points. And for visibility, I've tracked the cell up here. So this is always the cell corresponding to the same point. If epsilon is very small, we're in the unbalanced regime, then mass only transports to the small ball around this point. And now if you turn up the length, if you turn down the length scale and make transport cheaper, then you recover this more classical Wastegs-Dan-Truh behavior. So now the cell doesn't even contain the point anymore. So the point is still here, but its corresponding cell has now moved to ball. And down here you can see the emerging this structure of these small balls. I think it's very nice to play with these features. And I guess it has an application somewhere. We'll figure it out eventually. OK. So now we have the length scale. So we understood now the semi-district number less transport problem to some extent. Now we think of further, let's look at the so-called quantization problem. So what is it? Our goal is now to approximate some absolutely, Lebesgue-Azul continuous measure mu by MD-RAC masses in the optimal transport sense. So we're trying to minimize the following object. We're trying to minimize the transport distance from mu to nu, where nu is now a superposition of MD-RAC measures. And we're optimizing the locations and the masses. This has applications I've been told in optimal location planning. For instance, if mu are your customers and they live spread out over the countryside and you want to build discrete stores, whether you build them, you try to minimize this essentially. Or apparently in physics, it's related to the pattern formation in crystals. We'll get to that. Or if you just want to discretize something for the sake of numerics. So it has its merits to this problem, so let's just look at it for now. Well, one way to tackle this is to first get rid of the minimization of the masses. So we're doing this first. And we will arrive at a problem of this form, where we just minimize over the positions. And we have to guess what this JM is now. Well, if we're free to choose the mass that we want, what we can do is for every mass of mu, we always pick the closest point. There's no need to go to another point, which always pick the nearest neighbor. And that means that the optimal coupling will be mu chopped up into the Voronoi diagrams now. So every particle of mu is going to the closest point. And then we put all of this to xi. And then we just choose the masses Mi to be exactly that kind of mass that's arriving. Then we're good to go. This is very easy. And then this JM becomes this very simple formula. So we're integrating over each cell the transport from that cell to its generating point. Very simple. Very easy to solve essentially. Now it's not very simple to solve because it's highly non-convex and x, but apart from that, I think it's decently treatable. OK, now let's do the same thing in the unbalanced case again. We have some practice by now. All right, so all I'm doing is adding and writing a few things. We changed optimal transport to unbalanced here. Again, I am assuming that we prefer to balance the mass if possible. And now we'll stop optimizing over the m again. As before, we know that whatever we're very much of mu, we will chop it up into the Voronoi cells and transport everything into the generating point. And we will choose the mi to be equal to the mass that arrives, that is just as before. And then all that is left is this row. We have to find it. So this j will be the infomization over this row of. Now here we have the transport term. Everything in cell vi is transported to xi. Now here we have the marginal discrepancy term on the first marginal. We have to pay for the deviation between row and mu. And finally, that would be the second marginal term, but we've eliminated that by setting m to be this mass. And then due to this assumption, this guy disappears. So we're only stuck with this guy. We have to infomize over row. And due to this guy here, we can infomize over rows that are dominated by mu. And we can essentially optimize over the density. And if you look at this long enough, we just pull out a minus. Then this is a supremum. There's a minus. Now here's a minus. And then this is essentially a central shawntry conjugation pointwise. And we end up, again, with our favorite function minus f star of minus something. And again, compared to before, it's almost the same thing. We just have to add this guy. Very simple. Very nice. And the optimal free marginal, we end up by doing this optimization. We know what it is. All right. So the unbalanced quantization problem seems to be also like everything continues to live on. The unbalanced thing hardly destroys any structure. OK. Now, a numerical method just to get some pictures. In the balanced case, you would use what is called Lloyd's algorithm, or you could use it. And the idea behind this is essentially an alternative optimization. First, for given points x1 to xm, you compute the optimal coupling, which essentially only means you need to find this for annoy cells. And then for the fixed coupling, you optimize the locations. So for every point xi, you try to put it such that the transport from the cell to that point will be keep the cell fixed. It's now minimal. So the new xi will be the generalized weighted center of mass of this old cell. And you just iterate this, and there's a bunch of literature on this, which will usually converge to a critical point. Not necessarily to a global optimizer, but to a critical point of the function. And again, all we have to do in the unbalanced cases, we have to replace this guy by rho. And we have to add our minus f star of minus. And everything else remains. This is still a weighted center of mass just for a different weight function. So even some of the convergence proofs here still apply. We didn't even have to worry about this. So we can apply Lloyd's algorithm with very minimal changes. And now here we have some examples some numerical ones. So again, we start with Wasserstein 2 just to get an idea of what we're expecting. Here we have a slightly homogeneous density. So it's a bit lower at the boundaries, and it's higher in the center. And if you quantize this, then you get a roughly equal distribution of points. Every chunk here is covered by one of these points. Now in the unbalanced setting, you see a quality to see very different behavior. In particular, all the points and all of these three models, they're concentrating around the center. So the length scale here is chosen such that these balls cannot longer cover the full space. So they have to compromise some. They cannot approximate all the mass. They have to compromise. What do they do? Of course, they go there with the masses highest. It's a very natural phenomenon, and you can see it's pre-universal in all three models. When it turns out, this may actually be related to things that we see in real life. This is the population density of Germany. And we just run a quantization method on this just to have a nice picture for the paper. And we got this. And then Benedict realized, well, if I look up the distribution of Ikea stores in Germany, this seems strangely similar. So in Berlin, there's a bunch. There's a few in Hamburg, in Bavaria. This is actually only once in Nürnberg and Munich. And there's a lot of them in multi-invest files. I don't know what the English name of that is. A few in Baden-Württemberg, but virtually nobody in Brandenburg on making book 4.4.1 can go to Ikea. Because Ikea simply says, OK, I can cover everything. I have to make a compromise. And that compromise is making book 4.4.1. So I think that the unbalanced potential problem actually may be able to describe things that we see in real life. So it's not an entirely academic problem. OK. Now, the final part of this talk, and I'm usually a lot faster than I intended to. But this gives you more time for the final part. This is the most interesting one. So now we look at the quantization problem. Again, we try to minimize for these locations. But now we're going to look at the limit of very, very many points, like asymptotically infinity many points. So first of all, for technical reasons, we have to assume that x is now a complex polygon in R2. Otherwise, we couldn't do the math. And it has to have a most exciting, but that's not really important. It's important for technical reasons, but not for what I'm going to talk about. And then the other thing is that I'm introducing again this length scale epsilon here. Because if I let m go to infinity, then there will be points almost everywhere. And transport will always be very cheap. And I'm not seeing a lot. So I have to rescale accordingly. And I'm doing this where this epsilon. And it's actually very easy to see that if you're interested now in the limit of m going to infinity, the minimization of this guy with a sequence of epsilon m's that also goes to 0, then what you end up essentially is this guy. And I'm trying to explain this now. So first of all, here we have the asymptotic rescaled point density. So here this epsilon is just for rescaling. We have the number of points over the volume. So this is the asymptotic point density. And this function b is the energy density that you would get with a corresponding regular hexagonal tiling. So if you put over all of the area just regular triangular points in the corresponding veranoicelles of an hexagonal tiling, then you can assign an energy density to that. And this is this energy density. And what you get is actually area times this energy density. So this tells us that asymptotic and the optimal solution will be a regular triangular grid on our problem. This is not just for the back measure. Then everything falls essentially from this guy because this guy gives us a lower bound than this one. And then we just have to construct a candidate for the upper bound and show that it converges. It's not that hard. Now, in the under balance case, again, almost everything survives. We have to add this minus f star of minus, which only affects this guy here, but the theorem still remains applicable and we get the same result. I think for technical reasons, we assumed we were lazy. We assumed that f of 0 is somewhere between 0 and infinity. This not 0 because then otherwise it would be trivial. We don't have to transport it all. And not infinity because then we still have to do good answer to check. Is there a point covering this region? Otherwise, we have to move a point there. It was very annoying. You don't really learn a lot from this. We just said, nah, it's fine. And we're good. So you can extend the proof easily. It's just a lot of nitty-gritty work. OK, now what we get is this energy density B is now a non-negative. That's not surprising. It's decreasing. That's also not surprising. If you add more points, we can decrease the transport cost. It's convex. I did not expect that, but OK. And it continues. And if you let the point density go to 0, then the energy density will go to the cost that it takes to remove the mass completely by the under balance effect. And if you let the point density go to infinity, then it tends to 0 because you don't have to transport anymore. So this is all very natural. And this is the Lebesgue case. And now we can go to a slightly more challenging case with a varying density. Now x is still a polygon with the most excites. It's a convex polygon. Mu is now Lebesgue absolutely continuous with the Lipschitz continuous density m. And again, now we have three different regimes. If we let m go to infinity, if the corresponding rescale density goes to infinity, then we are getting the pure transport perfume. We don't care about the under-balanced effects. We just do transport. The cost goes to 0. Because there's points everywhere. In the other case where the scale point density goes to 0, we can't transport anymore because the points are now they seem very far away. So we have to do everything via the under-balanced effect. So it tends to go into removing all the mass with this f of 0. That's also very natural. The interesting part is now what happens in between. If this tends to a finite rescale density. And what we get is this guy, so limit of m to infinity of the minimize of this guy with m and epsilon m tends to this minimization problem. There we now integrate over the domain this point density function times the area. And d of x is now the spatially varying point density. So what you can see here is it will locally look like a regular hexagonal grid, but with varying length scales. And the length scale will depend on where we are. This is this function d of x. Well, what is this function d of x? It's something l1. It's positive. And if we integrate all the point densities, it has to come up to be this p. So we just have to choose this d such that this constraint is satisfied. And then we have to choose it in such a way that this is optimal. So locally, we have a hexagonal grid, which has to distribute our points in such a way that the cost is optimal. Well, and then you can, at least formally, you can see where this is going. If we are under the back case, then d will probably be a constant in space. Then we can just solve this guy. And then d will be p over x. And we're back to the original result from the previous slide. Now, if this is not constant, then we have to minimize over d, substitute this constraint. And what we will get is there is a dependency of x. Some function of the local mass density. And there's a lambda, which is essentially just the Lagrangian multiply of this guy. So there's a non-local, spatially-varied point density. And in the standard bussage-denture case, this is just the square root of the mass density, of the mass density, which just tells us if there's a lot of mass, I have to put more points there. Because even transporting to this point is more expensive. Like in points with math, forget about it. Yeah, I mean, you get the idea. When there's more mass, you have to put more points there. I think that makes sense. The interesting part is that in the unbalanced case, this d may become 0, even in areas where there's actually finite mass. This doesn't happen in the optimal transport case. There will always be a few points. But in the unbalanced case, d may drop to 0, even if there is mass lying there. And you can actually see that numerically very nicely. So we start with a, we keep m fixed. And we have a very small length scale. So it covers the whole space easily. So everything is covered. And now we've reduced epsilon. And at some point, it starts to lose total coverage. And it concentrates in the middle. So here you can see there's finite mass. But we do not cover this with points. We had this earlier. But now if we let m go to infinity and decrease m, it's epsilon in such a way that this remains constant, you can see very nicely that the area that is covered roughly stays the same. And it tends to be a beautiful hexagonal group. So this is kind of a numerical confirmation, if you will, of this result here. We have no point density here. We have quite a constant point density in the other areas. And we can compute this asymptotic point density by looking at this guy. It's not that hard to do this. And then what we get is for this input density, which is the same as before, just a different color scale, if we now decrease the number of points that is available, so this rescale point density, if we just decrease it, it starts to chop off regions. And he focuses more and more on the highest density regions. And the same thing happens in this population with Germany density example. You can see in the beginning that IKEA everywhere. But if we decrease the number of stores available, then eventually only the people in the rural area and in Berlin will be able to go to IKEA and everyone else. I have to get to this for each other elsewhere, I don't know. So this is very interesting phenomenon. It's pretty intuitive to, of course, the form improves a bit harder. But if you look at this, it's pretty intuitive to see where this is coming from. And I'm very happy that David came to visit us and that we stumbled into this problem. And I think that is more or less it. Summary, everything survives. It has a relation formulation. But you have this very interesting interplay of the length scale between the mass change and the transport. In the quantization problem, Lloyd's algorithm survives. But now we have this new feature of these neglected regions. And in crystallization, still the classical result survives. We have a model triangular grits. And we have this non-trivial local point density thing. Just by the way, I'm moving to Munich next month. I'm seeking to hire a PhD student in the numerical transport. So if you have a candidate that you do not want to keep for yourself, I'm happy. If you let him know of this. All right, thank you very much. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. OK, time for questions. Any questions for Bernard? You changed the underlying distance, the occulting distance. Yes? Do you consider something unethic topic? Basically, with an unethic topic, wave shape underneath, do you get potentially at the end also other microscopic patterns? I think we talked to David about this. I'm really not an expert on crystallization. My impression is that as long as it's nothing too fancy, I think yes. We will just be, if it's ellipsoid, for instance. So our easiest case would be an infinity one. And then, who is an expert? I would expect that you get a different grid, maybe, with an infinity might be just squares. I'm really just guessing here. Or, yeah. And what are the squares? Diamonds? Oh, it's magic. Do it. So because of the UK's times. My impression is that whatever survives in the balance case might survive in the unbalanced case. So if the optimal tasselation in infinity is diamonds, then I guess it will remain diamonds. That would be my intuition. But we didn't check. Yes? So in the balanced case, when the cell, the some cell disappear, then the action degenerates. Then the action of the function degenerates. And then the constant of the problems. So what happens in your case? Oh, that's an interesting question. So what about the linear case? Yes, because did you code the Newton's method? No, no. We used the quasi-Newton method at some point. But we didn't bother evaluating the Hessian. What I think is there some kind of magic compensation from the. So for instance, if you use faster than the Scharal, it will be very tedious because then the lines will no longer be straight lines. I think if you use the Gaussian and Euler-Konatorvich thingy, then you still have straight, you still have standard like air cells. So then you still have straight lines which you could evaluate. And the Hessian, I don't think the Hessian has a meaning in that case. We would just, I think, we would be a king. I mean, there will still be a derivative. It's not completely degenerate because there will be the F0 term, I guess. But I don't think it will be C2. Sure? Maybe it depends on how F behaves at 0. So no, I'm absolutely not sure. Because in the case of the sphere, the case of the sphere with this log is essentially a feature of cost. Then it's equivalent to compute this cells and standard of the matchments for cells. So for different costs, which has been implemented by Compte-Merigou and is able to make by next second order of optimization. But I understand that to do this numerically, at least, you need to be able to handle the interface very elegantly. And this is. Yes, but the interface in the case of the sphere is kind of easy. For this cost function? For the Vessar-Stefichon. OK, I was not aware of that. OK. You use the same function F for the source and the target. Is it essential? No. No. If you want to go to metric. I think you can. Yeah, because we came from the master-scientific raw case, but there's absolutely no reason in the analysis to do that. In complex analysis, there are other ways of combining energy functions or cost functions, particularly in the context case, there's this evolution. How would this relate to what you're doing? Well, it's kind of an internal convolution. This is a bit like internal convolution, right? This is exactly. Oh, OK. In a Romanian sense. I mean, you can always choose either go this direction or go this direction. Any composition on that? Otherwise, I think you can also interpret this as you have an interior transport. And then on the outside, you have additional terms that paralyze the. So you can write this as a nested optimization. That will also be an internal convolution. Not exactly an internal convolution, but because you don't have the minus, but apart from that, we'll look very similar. You have questions? If you will, please. Thank you.
 That's the setting.  And then, of course, you all know that in the case  that x length space, then also the resulting  Wasserstein space will be a length space.  That means there will be shortest path, which  correspond to the so-called displacement interpolation.  So instead of just doing the linear interpolation  between two measures, we're actually moving mass  in the base space.  And then we can associate a momentum field with this,  or a velocity field.  And it turns out you can actually rewrite the whole transport  problem in terms of these fields of the mass and the momentum  field, satisfying the continuity equation in a weak sense.  And then you minimize this action,  which is essentially the kinetic energy integrated in toy.  Yeah, and if you set p equal to 2,  this looks a lot like Ray-Banian-Baniforce.  I'm just doing this because I will briefly  want to talk about unbalance optimal transport,  because I don't think everyone's familiar with this.  So this is the motivation.  Let's see.  We have a problem like that.  We have two bunches of mass here in the beginning  and two different batches of mass in the end.  We want to interpolate.  And if they're not equally split up,  then there will be no choice but to transport a bit of mass  from one to the other one.  And if this is just a tiny measurement error,  and this is very far apart, then this  is a very unnatural behavior.  You want to get rid of this.  Well, things actually maybe have to grow or shrink.  If we want to model this, we want a behavior like that.  Well, one way to do this is starting  from this Ben-Aubigny formula, just modified  to make it unbalanced.  So we add a source term, theta, here,  which appears here in the continuity equation.  And then we have to modify our action  to penalize the theta as well.  So we remove the kinetic energy and we  add something which contains theta.  And the idea is not that new.  And in fact, a lot of different things for phi  have been tried, more like TV-type things for theta,  L1-type, or combined L1 and L2 things.  And the thing I want to focus on today  is this particular term, which we  call the vasestant-discharal distance.  And other people came up with it as well.  For instance, Euromucan-Savare called it  the Helio-Konturvitsch distance.  And what you can see here is, essentially, we  have here the optimal transport part.  And here we add a term which looks  like the remaining tensor of the visceral distance.  So this is the Riemannian tensor of vasestant.  This is the Riemannian tensor of visceral.  We just combine it.  Gives it a bit more options to handle solutions here.  OK.  Now, the good news is this new object indeed  does yield the geodesic distance on non-negative measures.  And just to see a bit more what it does, what it structures,  we looked at geodesic between direct measures.  So we started with the direct x0, mass 0,  when I go to x1, m1.  And then the standard vasestant measurement  would happen is, if both m's are equal,  then the geodesic is a Dirac moving at constant speed  from the initial to the final location.  Now, in the Fischer-Rauke case, in the Vasestant-Diescher-Rauke  case, if the two Diracs are sufficiently close,  closer than pi in this case, then the geodesic will also  be a traveling Dirac, but it will reduce its mass  bit in the middle to save on transport values.  So in the beginning, it will reduce the mass,  then transport is cheaper, and then  you have to grow the mass back.  And finally, when the masses are too far apart,  it turns out that transport is no longer economical,  and you do everything via the Fischer-Rauke term.  So the first Dirac is simply being teleported,  if you want, to a second Dirac.  And now, this is already a nice result, I think.  Diracs are staying Diracs.  They're not being destroyed or smeared out.  But the most, I think, most pleasant result  is that, in fact, general geodesics  can be decomposed into geodesics between Diracs.  So we kind of understand very nicely  what this distance is doing.  And here's a small numerical example.  So we have a density that we interpolate into another density.  If you just take the L2 or TV or whatever interpolation,  you just get this fading, not very satisfying.  If you do Rathenstein 2, you get, well,  you get movement of mass, right?  No more fading.  But here, for instance, you have this chunk of mass  that's traveling from the whole image from this square  to form this Q down there.  And this may be unpleasant.  This may be an artifact that you want to get rid of,  and in the unbalanced case, you get it.  Locally, you get nice interpolations,  but globally, there is no interaction between them.  So I think this has its merits in many applications.  OK.  Now, another way to tackle the unbalanced transport question  is to start from the Kantorovitch formulation.  So we started from Benjamin Bernier.  You could also start from Kantorovitch,  and you relaxed the marginal constraints.  So now you're optimizing over arbitrary,  not negative measures.  You pay the transport price.  And here, you penalize the deviation  of the first marginal from mu and the second marginal from mu  by some marginal discrepancy function, which usually has  some form, some integral of some small f.  And there's more choices, but today we only need this one,  where f is super linear, so it's going to be infinite  if it's not absolutely continuous with respect  to the marginal.  And then you can try to solve this.  You can go to the dual problem.  It looks very similar than before.  We have the same feasible set and the same constraints.  But now, it's no longer just the overlap of alpha with mu,  but now there's this minus f star minus.  And this is, in general, an increasing concave function.  So this is still a convex optimization problem,  concave maximization problem.  All right.  And you can recover the balanced case very easily  by setting f to be the indicator function of 1.  Then here, rho has no choice but to be equal to mu.  Otherwise, this will be infinity.  And then if you do this conjugation,  you will get that this function is indeed the identity.  So these terms simply disappear when  you have the original dual problem.  And now, the most elegant or beautiful result of all this  that actually there's a bridge between those two approaches.  You can recover this, but then, for our handling  of the distance by setting this marginal  is pregnancy to the kubat-Liber divergence.  And the cost factor of this particular cost function.  You don't need to worry about the details.  This is just some function.  But this is a radial cost.  This is an increasing function of the distance.  And it will be infinity after, oh, I  didn't adapt the normalizations after pi half.  So this is a slightly different trade  between transport and mass change.  So there will be no transport further than this.  Beyond the system, everything has to be handled by kubat-Liber.  OK.  Then the final thing that we need, the final ingredient,  before we can put everything together,  is semi-discreet transport.  So now mu will be an absolute continuous measure.  And mu will be a discrete measure of some Dirac's  with mass mi at locations xi.  Then we can almost immediately tell  that the form of the optimal coupling  has to be something like this.  So we chop up mu into cells ci.  And then everything in the cell ci  is being transported to xi.  This has to be the form of the optimal coupling.  And these cells ci that are the so-called generalized  like air cells.  So for a weight vector w, we just check where is it.  This thing is maximal.  And all the points x, where this is maximal,  they are in cell ci.  So this is related to the C transport.  Of course, you will know this is optimal transport.  And in our case, since the cost may be infinite,  there may be a residual set where  we cannot go with finite cost.  And this will be treated separately occasionally.  OK.  If you haven't seen those guys, just  think of this as the generalization of the Voronoi cells.  If you just pick c to the distance  and you set this weight vector to 0,  this is just the Voronoi cells.  But you see, if I turn up certain w,  I can make this smaller.  And so I will increase the corresponding cell.  You can do a bit of competition between the different cells.  And then starting from this, you can go back  to the original transport problem.  And you will get that in the semi-discrete case,  you can solve optimal transport with this tessellation  formulation, where this is essentially,  you can get from the dual to this very quickly.  So our dual measure nu, sorry, only lives on these points xi.  So we only need the dual variable beta at these points.  So this will be the dual variable beta only at those locations.  So this is the original dual term.  And then we just pick the optimal alpha for a fixed beta.  We make alpha as large as possible.  It has to be smaller than all the dual constraints.  And this is the dual constraint that will be active  on this particular cell.  So this is a very simple transformation.  And you will get to this particular formulation.  And in fact, this is also the base point  for very efficient numerical methods.  That contact, for instance, is working on.  You want to get that by Bruno Levy?  OK, I think now we have all the ingredients assembled.  Now we can combine them.  So the first good news is this dual tessellation formulation  survives.  Now the optimal coupling is a slightly more general form.  We still chop up some measure and transport everything  in the corresponding cell to the corresponding point.  But now this measure that we chop up is no longer necessarily  equal to mu, but it can be something else due to the  marginal discrepancy.  Then if you look at the dual formulation, you can do the  same trick.  We introduce this new effective dual variable w.  And then we just pick the corresponding alpha as large  as possible, which we result in this guy.  And instead of just being the overlap between the two, we  have this minus f star minus appearing both in the alpha  and in the beta term.  And then there's the residual term, things that cannot be  reached.  We have no choice but to remove this mass.  We have to pay f zero for this.  So the balanced case, this would be a problem, because  then this is infinity.  But in the unbalanced case, this might still be OK.  So this is the dual tessellation formulation.  It survives almost unchanged.  And now in this case, again, we recover the balanced case.  It's very easy.  But now we can also do a primal version of this.  So we take these kinds of couplings, and we don't know  the rho yet, and we don't know the w yet.  We can just plug it into the primal one and optimize over  those two guys.  We optimize over omega s.  And w, and we're probably going to optimize over rho.  And there cannot be any mass in the residual.  And then you get this is the transport term for every cell  to transport to the cross-point.  This is the first marginal discrepancy.  This is the second marginal discrepancy.  It's very natural.  And this doesn't really make sense in the balanced case,  because it would only be finite when it's optimal.  Because this is only finite when the second marginal  constraint is satisfied.  This is only finite when the first marginal constraint is  satisfied, and then you know they're already optimal.  So it doesn't really make sense in the balanced case, in the  unbalanced case.  I think it's natural to write this thing down.  OK, let's go further.  Let's try a few things.  Now we have choices to make.  We have cost function, and we have this marginal  discrepancy to choose.  So we can get very different behavior.  So let's start with the standard  Wasserstein 2 case to practice.  We just take the square distance, and we take this f to  be the indicator function of 1, which means that  calligraphic f can only be the indicator function of mu.  So the marginal is actually fixed.  Then these cell CI will be actually the weighted Laguerre  cells with piecewise straight lines.  And there will be no residual, and the marginal rho has no  choice but to be equal to mu.  So this is the back measure that I'm currently just using as  the first marginal.  And now in the Wasserstein 2 case, it's just chopped up into  these cells, and every cell is transported onto this point.  So now let's start unbalanced.  Now we change f to be the calligraphic letter divergence.  Now the first marginal is free.  And what happens is the cells are still weighted like air  cells.  They're slightly different, but the shape is the same,  essentially.  And now the first marginal is free, and you see that it's  a bit as higher density when you close the points, because  then it's cheaper to transport.  And the density is decreased if you're far from the point,  because you don't want to transport as much.  So that's very natural.  And in this particular case, you will notice that the support  of this new free measure rho is now still the whole space,  because this calligraphic letter divergence is  essentially minus infinite slope at 0.  So even if you're very far, and it's very expensive to  transport, it's still cheaper to transport a very little bit  to gain a bit of this infinite slope.  So this measure still has infinite support.  Full support.  Now we go to this Wasserstein Fisher-Rauw case.  So we keep the calligraphic letter divergence, and we  change the cost to this particular one, which is  infinite after the pi half.  Now what we get is, for the first time, we have a non-empty  residual set.  This is marked here in white.  These points, we cannot transport them to any of the  red points with the finite cost.  We have no choice but to send rho to 0 here.  Otherwise, it would be infinite.  But everywhere else, for the same argument as before,  everywhere else rho has support.  And finally, we tried quadratic regularization.  We just take, again, the standard Euclidean distance.  And now we penalize in a quadratic fashion the  deviation from the original marginal.  Then the residual set is now a non-empty because the cost is  finite.  So everything here is not white.  But still, the measure rho does not have full support.  Because here, it's a finite cost to transport to there, but  it's even cheaper to just neglect the mass completely.  So we have qualitatively very different behavior here.  Just the standard balance case.  There's not enough degrees of freedom.  Now here, it's almost the same just the  measure rho is varying a bit.  Now here, we have only bounded support.  And that's due to the infinite transport cost.  And here, we have bounded support.  But that is now due to the finite  throwing mass away cost.  We have four qualitatively very different behaviors.  That's a nice suit to play with.  OK.  And we also see that there's kind of a length scale  intrinsically involved in all of this.  The length scale between those, the distance of these points  and how far we can transport.  So now let's play with this length scale.  And for this, we look now at the scale of cost.  See epsilon, we just put an epsilon here.  So if my epsilon is very small, it will look like our space  is very large.  And transport will become very expensive.  And for simplicity, we just assume that f of 1 is equal  to 0.  That means if possible, we prefer to balance the masses.  And we pay for not balancing them.  OK.  Now this is the problem that we try to solve.  If we have epsilon go to infinity, then we can see here  that this is becoming very small.  And transport is becoming very cheap.  We're making the space very small.  So we don't really need to change the map.  We can transport everything with very little cost.  And it will go to 0, essentially.  If we let epsilon go to 0, then transport  will become prohibitively expensive.  And we have to do everything via the marginal constraints.  And here is what we can see.  For large epsilon, in this case, large means 1.  This is the back measure.  It's transported onto those four points.  And you don't see anything.  This is constant.  Now if you make epsilon smaller and smaller,  transport is becoming more expensive.  And what you can see here in the cells,  the standard, they're no longer the generalized  like air cells, but now they're becoming curved.  And now you can see here, you can see the residual popping up.  So now the unbalanced effects show up  if you make epsilon smaller and smaller.  And also you can see here in the free marginal row,  in the beginning it's essentially  equal to the back measure.  And you can start to see this emphasis near the points where  you can actually transport to.  So this is very natural.  And here's the same example with a bit more points.  And for visibility, I've tracked the cell up here.  So this is always the cell corresponding to the same point.  If epsilon is very small, we're in the unbalanced regime,  then mass only transports to the small ball around this point.  And now if you turn up the length,  if you turn down the length scale and make transport cheaper,  then you recover this more classical Wastegs-Dan-Truh  behavior.  So now the cell doesn't even contain the point anymore.  So the point is still here, but its corresponding cell  has now moved to ball.  And down here you can see the emerging  this structure of these small balls.  I think it's very nice to play with these features.  And I guess it has an application somewhere.  We'll figure it out eventually.  OK.  So now we have the length scale.  So we understood now the semi-district number less  transport problem to some extent.  Now we think of further, let's look at the so-called quantization  problem.  So what is it?  Our goal is now to approximate some absolutely,  Lebesgue-Azul continuous measure mu by MD-RAC masses  in the optimal transport sense.  So we're trying to minimize the following object.  We're trying to minimize the transport distance from mu  to nu, where nu is now a superposition of MD-RAC measures.  And we're optimizing the locations and the masses.  This has applications I've been told in optimal location  planning.  For instance, if mu are your customers  and they live spread out over the countryside  and you want to build discrete stores,  whether you build them, you try to minimize this essentially.  Or apparently in physics, it's related to the pattern  formation in crystals.  We'll get to that.  Or if you just want to discretize something  for the sake of numerics.  So it has its merits to this problem,  so let's just look at it for now.  Well, one way to tackle this is to first get rid  of the minimization of the masses.  So we're doing this first.  And we will arrive at a problem of this form,  where we just minimize over the positions.  And we have to guess what this JM is now.  Well, if we're free to choose the mass that we want,  what we can do is for every mass of mu,  we always pick the closest point.  There's no need to go to another point, which always  pick the nearest neighbor.  And that means that the optimal coupling  will be mu chopped up into the Voronoi diagrams now.  So every particle of mu is going to the closest point.  And then we put all of this to xi.  And then we just choose the masses Mi  to be exactly that kind of mass that's arriving.  Then we're good to go.  This is very easy.  And then this JM becomes this very simple formula.  So we're integrating over each cell  the transport from that cell to its generating point.  Very simple.  Very easy to solve essentially.  Now it's not very simple to solve because it's highly  non-convex and x, but apart from that,  I think it's decently treatable.  OK, now let's do the same thing in the unbalanced case again.  We have some practice by now.  All right, so all I'm doing is adding and writing a few things.  We changed optimal transport to unbalanced here.  Again, I am assuming that we prefer  to balance the mass if possible.  And now we'll stop optimizing over the m again.  As before, we know that whatever we're  very much of mu, we will chop it up  into the Voronoi cells and transport everything  into the generating point.  And we will choose the mi to be equal to the mass that  arrives, that is just as before.  And then all that is left is this row.  We have to find it.  So this j will be the infomization over this row of.  Now here we have the transport term.  Everything in cell vi is transported to xi.  Now here we have the marginal discrepancy term  on the first marginal.  We have to pay for the deviation between row and mu.  And finally, that would be the second marginal term,  but we've eliminated that by setting m to be this mass.  And then due to this assumption, this guy disappears.  So we're only stuck with this guy.  We have to infomize over row.  And due to this guy here, we can infomize over rows  that are dominated by mu.  And we can essentially optimize over the density.  And if you look at this long enough,  we just pull out a minus.  Then this is a supremum.  There's a minus.  Now here's a minus.  And then this is essentially a central shawntry  conjugation pointwise.  And we end up, again, with our favorite function minus f star  of minus something.  And again, compared to before, it's almost the same thing.  We just have to add this guy.  Very simple.  Very nice.  And the optimal free marginal, we end up  by doing this optimization.  We know what it is.  All right.  So the unbalanced quantization problem  seems to be also like everything continues to live on.  The unbalanced thing hardly destroys any structure.  OK.  Now, a numerical method just to get some pictures.  In the balanced case, you would use what  is called Lloyd's algorithm, or you could use it.  And the idea behind this is essentially  an alternative optimization.  First, for given points x1 to xm,  you compute the optimal coupling, which essentially only  means you need to find this for annoy cells.  And then for the fixed coupling, you optimize the locations.  So for every point xi, you try to put it such  that the transport from the cell to that point  will be keep the cell fixed.  It's now minimal.  So the new xi will be the generalized weighted center  of mass of this old cell.  And you just iterate this, and there's  a bunch of literature on this, which  will usually converge to a critical point.  Not necessarily to a global optimizer,  but to a critical point of the function.  And again, all we have to do in the unbalanced cases,  we have to replace this guy by rho.  And we have to add our minus f star of minus.  And everything else remains.  This is still a weighted center of mass  just for a different weight function.  So even some of the convergence proofs here still apply.  We didn't even have to worry about this.  So we can apply Lloyd's algorithm with very minimal changes.  And now here we have some examples some numerical ones.  So again, we start with Wasserstein 2  just to get an idea of what we're expecting.  Here we have a slightly homogeneous density.  So it's a bit lower at the boundaries,  and it's higher in the center.  And if you quantize this, then you  get a roughly equal distribution of points.  Every chunk here is covered by one of these points.  Now in the unbalanced setting, you see a quality  to see very different behavior.  In particular, all the points and all of these three models,  they're concentrating around the center.  So the length scale here is chosen  such that these balls cannot longer cover the full space.  So they have to compromise some.  They cannot approximate all the mass.  They have to compromise.  What do they do?  Of course, they go there with the masses highest.  It's a very natural phenomenon, and you  can see it's pre-universal in all three models.  When it turns out, this may actually  be related to things that we see in real life.  This is the population density of Germany.  And we just run a quantization method on this  just to have a nice picture for the paper.  And we got this.  And then Benedict realized, well, if I look up the distribution  of Ikea stores in Germany, this seems strangely similar.  So in Berlin, there's a bunch.  There's a few in Hamburg, in Bavaria.  This is actually only once in Nürnberg and Munich.  And there's a lot of them in multi-invest files.  I don't know what the English name of that is.  A few in Baden-Württemberg, but virtually nobody in Brandenburg  on making book 4.4.1 can go to Ikea.  Because Ikea simply says, OK, I can cover everything.  I have to make a compromise.  And that compromise is making book 4.4.1.  So I think that the unbalanced potential problem actually  may be able to describe things that we see in real life.  So it's not an entirely academic problem.  OK.  Now, the final part of this talk, and I'm usually  a lot faster than I intended to.  But this gives you more time for the final part.  This is the most interesting one.  So now we look at the quantization problem.  Again, we try to minimize for these locations.  But now we're going to look at the limit of very, very many  points, like asymptotically infinity many points.  So first of all, for technical reasons,  we have to assume that x is now a complex polygon in R2.  Otherwise, we couldn't do the math.  And it has to have a most exciting,  but that's not really important.  It's important for technical reasons,  but not for what I'm going to talk about.  And then the other thing is that I'm introducing again  this length scale epsilon here.  Because if I let m go to infinity,  then there will be points almost everywhere.  And transport will always be very cheap.  And I'm not seeing a lot.  So I have to rescale accordingly.  And I'm doing this where this epsilon.  And it's actually very easy to see  that if you're interested now in the limit of m going  to infinity, the minimization of this guy  with a sequence of epsilon m's that also goes to 0,  then what you end up essentially is this guy.  And I'm trying to explain this now.  So first of all, here we have the asymptotic rescaled point  density.  So here this epsilon is just for rescaling.  We have the number of points over the volume.  So this is the asymptotic point density.  And this function b is the energy density  that you would get with a corresponding regular hexagonal  tiling.  So if you put over all of the area just regular triangular  points in the corresponding veranoicelles  of an hexagonal tiling, then you  can assign an energy density to that.  And this is this energy density.  And what you get is actually area times this energy density.  So this tells us that asymptotic and the optimal solution  will be a regular triangular grid on our problem.  This is not just for the back measure.  Then everything falls essentially from this guy  because this guy gives us a lower bound than this one.  And then we just have to construct a candidate  for the upper bound and show that it converges.  It's not that hard.  Now, in the under balance case, again, almost everything  survives.  We have to add this minus f star of minus, which only  affects this guy here, but the theorem still remains applicable  and we get the same result.  I think for technical reasons, we assumed we were lazy.  We assumed that f of 0 is somewhere  between 0 and infinity.  This not 0 because then otherwise it would be trivial.  We don't have to transport it all.  And not infinity because then we still  have to do good answer to check.  Is there a point covering this region?  Otherwise, we have to move a point there.  It was very annoying.  You don't really learn a lot from this.  We just said, nah, it's fine.  And we're good.  So you can extend the proof easily.  It's just a lot of nitty-gritty work.  OK, now what we get is this energy density B  is now a non-negative.  That's not surprising.  It's decreasing.  That's also not surprising.  If you add more points, we can decrease the transport cost.  It's convex.  I did not expect that, but OK.  And it continues.  And if you let the point density go to 0,  then the energy density will go to the cost  that it takes to remove the mass completely  by the under balance effect.  And if you let the point density go to infinity,  then it tends to 0 because you don't  have to transport anymore.  So this is all very natural.  And this is the Lebesgue case.  And now we can go to a slightly more challenging case  with a varying density.  Now x is still a polygon with the most excites.  It's a convex polygon.  Mu is now Lebesgue absolutely continuous with the Lipschitz  continuous density m.  And again, now we have three different regimes.  If we let m go to infinity, if the corresponding rescale  density goes to infinity, then we  are getting the pure transport perfume.  We don't care about the under-balanced effects.  We just do transport.  The cost goes to 0.  Because there's points everywhere.  In the other case where the scale point density goes to 0,  we can't transport anymore because the points are now  they seem very far away.  So we have to do everything via the under-balanced effect.  So it tends to go into removing all the mass with this f of 0.  That's also very natural.  The interesting part is now what happens in between.  If this tends to a finite rescale density.  And what we get is this guy, so limit of m to infinity  of the minimize of this guy with m and epsilon m  tends to this minimization problem.  There we now integrate over the domain  this point density function times the area.  And d of x is now the spatially varying point density.  So what you can see here is it will locally  look like a regular hexagonal grid,  but with varying length scales.  And the length scale will depend on where we are.  This is this function d of x.  Well, what is this function d of x?  It's something l1.  It's positive.  And if we integrate all the point densities,  it has to come up to be this p.  So we just have to choose this d such that this constraint  is satisfied.  And then we have to choose it in such a way that this is optimal.  So locally, we have a hexagonal grid,  which has to distribute our points in such a way  that the cost is optimal.  Well, and then you can, at least formally,  you can see where this is going.  If we are under the back case, then d will probably  be a constant in space.  Then we can just solve this guy.  And then d will be p over x.  And we're back to the original result from the previous slide.  Now, if this is not constant, then we  have to minimize over d, substitute this constraint.  And what we will get is there is a dependency of x.  Some function of the local mass density.  And there's a lambda, which is essentially just  the Lagrangian multiply of this guy.  So there's a non-local, spatially-varied point density.  And in the standard bussage-denture case,  this is just the square root of the mass density,  of the mass density, which just tells us  if there's a lot of mass, I have to put more points there.  Because even transporting to this point  is more expensive.  Like in points with math, forget about it.  Yeah, I mean, you get the idea.  When there's more mass, you have to put more points there.  I think that makes sense.  The interesting part is that in the unbalanced case,  this d may become 0, even in areas  where there's actually finite mass.  This doesn't happen in the optimal transport case.  There will always be a few points.  But in the unbalanced case, d may drop to 0,  even if there is mass lying there.  And you can actually see that numerically very nicely.  So we start with a, we keep m fixed.  And we have a very small length scale.  So it covers the whole space easily.  So everything is covered.  And now we've reduced epsilon.  And at some point, it starts to lose total coverage.  And it concentrates in the middle.  So here you can see there's finite mass.  But we do not cover this with points.  We had this earlier.  But now if we let m go to infinity and decrease m,  it's epsilon in such a way that this remains constant,  you can see very nicely that the area that is covered  roughly stays the same.  And it tends to be a beautiful hexagonal group.  So this is kind of a numerical confirmation,  if you will, of this result here.  We have no point density here.  We have quite a constant point density in the other areas.  And we can compute this asymptotic point density  by looking at this guy.  It's not that hard to do this.  And then what we get is for this input density, which  is the same as before, just a different color scale,  if we now decrease the number of points that is available,  so this rescale point density, if we just decrease it,  it starts to chop off regions.  And he focuses more and more on the highest density regions.  And the same thing happens in this population  with Germany density example.  You can see in the beginning that IKEA everywhere.  But if we decrease the number of stores available,  then eventually only the people in the rural area  and in Berlin will be able to go to IKEA and everyone else.  I have to get to this for each other elsewhere, I don't know.  So this is very interesting phenomenon.  It's pretty intuitive to, of course,  the form improves a bit harder.  But if you look at this, it's pretty intuitive  to see where this is coming from.  And I'm very happy that David came to visit us  and that we stumbled into this problem.  And I think that is more or less it.  Summary, everything survives.  It has a relation formulation.  But you have this very interesting interplay  of the length scale between the mass change and the transport.  In the quantization problem, Lloyd's algorithm survives.  But now we have this new feature of these neglected regions.  And in crystallization, still the classical result survives.  We have a model triangular grits.  And we have this non-trivial local point density thing.  Just by the way, I'm moving to Munich next month.  I'm seeking to hire a PhD student in the numerical transport.  So if you have a candidate that you do not want to keep for yourself,  I'm happy.  If you let him know of this.  All right, thank you very much.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  OK, time for questions.  Any questions for Bernard?  You changed the underlying distance, the occulting distance.  Yes?  Do you consider something unethic topic?  Basically, with an unethic topic, wave shape underneath,  do you get potentially at the end also  other microscopic patterns?  I think we talked to David about this.  I'm really not an expert on crystallization.  My impression is that as long as it's nothing too fancy,  I think yes.  We will just be, if it's ellipsoid, for instance.  So our easiest case would be an infinity one.  And then, who is an expert?  I would expect that you get a different grid, maybe,  with an infinity might be just squares.  I'm really just guessing here.  Or, yeah.  And what are the squares?  Diamonds?  Oh, it's magic.  Do it.  So because of the UK's times.  My impression is that whatever survives in the balance case  might survive in the unbalanced case.  So if the optimal tasselation in infinity is diamonds,  then I guess it will remain diamonds.  That would be my intuition.  But we didn't check.  Yes?  So in the balanced case, when the cell, the some cell  disappear, then the action degenerates.  Then the action of the function degenerates.  And then the constant of the problems.  So what happens in your case?  Oh, that's an interesting question.  So what about the linear case?  Yes, because did you code the Newton's method?  No, no.  We used the quasi-Newton method at some point.  But we didn't bother evaluating the Hessian.  What I think is there some kind of magic compensation from the.  So for instance, if you use faster than the Scharal,  it will be very tedious because then the lines will no  longer be straight lines.  I think if you use the Gaussian and Euler-Konatorvich thingy,  then you still have straight, you still  have standard like air cells.  So then you still have straight lines  which you could evaluate.  And the Hessian, I don't think the Hessian  has a meaning in that case.  We would just, I think, we would be a king.  I mean, there will still be a derivative.  It's not completely degenerate because there will be the F0  term, I guess.  But I don't think it will be C2.  Sure?  Maybe it depends on how F behaves at 0.  So no, I'm absolutely not sure.  Because in the case of the sphere,  the case of the sphere with this log  is essentially a feature of cost.  Then it's equivalent to compute this cells  and standard of the matchments for cells.  So for different costs, which has been implemented  by Compte-Merigou and is able to make  by next second order of optimization.  But I understand that to do this numerically,  at least, you need to be able to handle the interface very  elegantly.  And this is.  Yes, but the interface in the case of the sphere  is kind of easy.  For this cost function?  For the Vessar-Stefichon.  OK, I was not aware of that.  OK.  You use the same function F for the source and the target.  Is it essential?  No.  No.  If you want to go to metric.  I think you can.  Yeah, because we came from the master-scientific raw case,  but there's absolutely no reason in the analysis to do that.  In complex analysis, there are other ways  of combining energy functions or cost  functions, particularly in the context case,  there's this evolution.  How would this relate to what you're doing?  Well, it's kind of an internal convolution.  This is a bit like internal convolution, right?  This is exactly.  Oh, OK.  In a Romanian sense.  I mean, you can always choose either go this direction  or go this direction.  Any composition on that?  Otherwise, I think you can also interpret this  as you have an interior transport.  And then on the outside, you have additional terms  that paralyze the.  So you can write this as a nested optimization.  That will also be an internal convolution.  Not exactly an internal convolution,  but because you don't have the minus, but apart from that,  we'll look very similar.  You have questions?  If you will, please.  Thank you.
201812110905-Schmitzer_lrv_0_251.png 201812110905-Schmitzer_lrv_252_1115.png 201812110905-Schmitzer_lrv_1116_3827.png 201812110905-Schmitzer_lrv_3828_5051.png 201812110905-Schmitzer_lrv_5052_5495.png 201812110905-Schmitzer_lrv_5496_5603.png 201812110905-Schmitzer_lrv_5604_8099.png 201812110905-Schmitzer_lrv_8100_10883.png 201812110905-Schmitzer_lrv_10884_11195.png 201812110905-Schmitzer_lrv_11196_11315.png 201812110905-Schmitzer_lrv_11316_12563.png 201812110905-Schmitzer_lrv_12564_12611.png 201812110905-Schmitzer_lrv_12612_12695.png 201812110905-Schmitzer_lrv_12696_13271.png 201812110905-Schmitzer_lrv_13272_14099.png 201812110905-Schmitzer_lrv_14100_14183.png 201812110905-Schmitzer_lrv_14184_14975.png 201812110905-Schmitzer_lrv_14976_17651.png 201812110905-Schmitzer_lrv_17652_21851.png 201812110905-Schmitzer_lrv_21852_24371.png 201812110905-Schmitzer_lrv_24372_26207.png 201812110905-Schmitzer_lrv_26208_26255.png 201812110905-Schmitzer_lrv_26256_28403.png 201812110905-Schmitzer_lrv_28404_33335.png 201812110905-Schmitzer_lrv_33336_34379.png 201812110905-Schmitzer_lrv_34380_34523.png 201812110905-Schmitzer_lrv_34524_39107.png 201812110905-Schmitzer_lrv_39108_40115.png 201812110905-Schmitzer_lrv_40116_40271.png 201812110905-Schmitzer_lrv_40272_40439.png 201812110905-Schmitzer_lrv_40440_41471.png 201812110905-Schmitzer_lrv_41472_41735.png 201812110905-Schmitzer_lrv_41736_44111.png 201812110905-Schmitzer_lrv_44112_44351.png 201812110905-Schmitzer_lrv_44352_44399.png 201812110905-Schmitzer_lrv_44400_45587.png 201812110905-Schmitzer_lrv_45588_46415.png 201812110905-Schmitzer_lrv_46416_48407.png 201812110905-Schmitzer_lrv_48408_48539.png 201812110905-Schmitzer_lrv_48540_48659.png 201812110905-Schmitzer_lrv_48660_49007.png 201812110905-Schmitzer_lrv_49008_49055.png 201812110905-Schmitzer_lrv_49056_49415.png 201812110905-Schmitzer_lrv_49416_50327.png 201812110905-Schmitzer_lrv_50328_50377.png