2
$\begingroup$

Hi, I am reading the book "Topics in Optimal Transportation" by Cedric Villani.

The Brenier's theorem states (among other things) that there is a unique transport plan for the optimal transport with the quadratic cost if the measure $\mu$ (to be transported toward $\nu$) does not give mass to small sets. (page 66)

A counter example, in the case of mu giving mass to small sets, is the case where $\mu$ and $\nu$ are measures on $\mathbb R^2$, concentrated on $\{(0,0),(1,1)\}$ and $\{(0,1),(1,0)\}$ respectively. In that case, there is no uniqueness. (page 67)

However, I am wondering why this is only the case when $\mu$ does not give mass to small sets. We can easily imagine a case where $\mu$ and $\nu$ are continuous but are made such that there is no uniqueness. For example, with an analogy with the example above, $\mu$ can spread its mass on a line between $(0,0)$ and $(1,1)$ with some thickness, and $\nu$ on a line between $(0,1)$ and $(1,0)$ with the same thickness (so the two lines are symmetric and don't have zero measure). In that case, I still see two possible transport plans... Same thing if we consider 2 gaussians centered at $(0,0)$ and $(1,1)$ in the first measure and at $(0,1)$ and $(1,0)$ in the second one....

Any idea ?

Thanks

Improve this question
$\endgroup$
4
  • $\begingroup$ Dear WhitAngl, I took a liberty to TeXify your post. You can rollback it if you don't agree with the edit. $\endgroup$
    – Andrey Rekalo
    Commented Nov 26, 2010 at 23:30
  • $\begingroup$ Thank you very much! I'm not used to these fancy html tricks since I'm mostly used to text-only newsgroups. Your edits are fine :) $\endgroup$
    – WhitAngl
    Commented Nov 26, 2010 at 23:43
  • $\begingroup$ "I still see two transport plans..." Care to elaborate? $\endgroup$
    – Willie Wong
    Commented Nov 27, 2010 at 0:05
  • $\begingroup$ for example with the gaussians (with same variance), I would either match the gaussian in (0,0) with the one in (0,1) and match the one in (1,1) with the one in (1,0). Alternatively, I could also match the one in (0,0) with the one in (1,0) and the one in (1,1) with the one in (0,1). In fact, I don't see what really changed by having gaussians instead of diracs :s $\endgroup$
    – WhitAngl
    Commented Nov 27, 2010 at 0:53

1 Answer 1

Reset to default
4
$\begingroup$

Because there's no reason to ship a whole gaussian en masse to the same target gaussian. It's cheaper to send all the mass that is to one side of the diagonal (line joining (0,0) to (1,1)) to one gaussian and the rest of the mass to the other side. The same is true for the thickened line.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ok, great, it makes sense. Thanks! Since I'm using a discrete formulation (a transportation simplex) to solve the mass transport, I'm wondering whether such non uniqueness issues can come up in the discrete setting (each "bin" of my histograms could be considered as dirac mass, isn't it?). $\endgroup$
    – WhitAngl
    Commented Nov 27, 2010 at 2:07
  • $\begingroup$ I mean : for uniqueness issues, if the histograms that I am transporting are 2 gaussians in 2D but discretized in bins, is it similar to the 0-measure case (each bin is considered as a dirac) or to the continuous case (after all they both represent gaussians) ? $\endgroup$
    – WhitAngl
    Commented Nov 27, 2010 at 2:39
  • $\begingroup$ First, what I wrote above is correct only if the target distribution are point masses at (0,1) and (1,0). Otherwise the details are more complicated. I am not an expert on this but it seems to me that nonuniqueness arises when there are symmetric relationships between the source and target distributions. And this can definitely arise with discrete distributions. But you can always try to break the symmetries by moving the point masses a little or better using a continuous source distribution. $\endgroup$
    – Deane Yang
    Commented Nov 27, 2010 at 3:26
  • $\begingroup$ mmmm.. finally I still have the problem with the gaussians : I agree the gaussians can be split and are not fully transported. But if we just look at the center of each gaussian, they can move in a non unique way similarly to the dirac example, isn't it ? The theorem shouldn't be stated as : "there is uniqueness, except for a set of point of zero measure" ? $\endgroup$
    – WhitAngl
    Commented Nov 28, 2010 at 1:46
  • 1
    $\begingroup$ Any statement of uniqueness is always "except for sets of measure zero". You can always transport arbitrary sets of measure zero to anywhere you want without changing the cost. $\endgroup$
    – Deane Yang
    Commented Nov 28, 2010 at 4:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .