1
$\begingroup$

Let $A,B$ be compact subsets of $\mathbb{R}^n$. Let $\mu_A$ (resp. $\mu_B$) be uniform probability measures over $A$ (resp. $B$). Then as a consequence of Brenier's theorem there is a one-to-one function $T: A\to B$ that transports $\mu_A$ to $\mu_B$, so that for each measurable set $S$, $\mu_A(T^{-1}(S)) = \mu_B(S)$, which minimizes $\int \Vert x-T(x)\Vert^2\text{d}x$. See Ball (2004) for a reference.

Can we bound $\Vert x-T(x)\Vert$ in terms of the Hausdorff distance $d_H(A,B)$? Recall $d_H(A,B)$ is defined as $$d_H(A,B)=\text{max}(\underset{a\in A}{\text{sup}}\, \underset{b\in B}{\text{inf}}\Vert a-b\Vert, \underset{b\in B}{\text{sup}}\, \underset{a\in A}{\text{inf}}\Vert a-b\Vert)$$

Intuitively I would expect that $$\underset{x\in A}{\text{max}}\Vert x-T(x)\Vert \le d_H(A,B)$$ but I don't see a way to prove or disprove the claim.

$\endgroup$

1 Answer 1

0
$\begingroup$

"Uniform probability measure" over a compact set is not a clearly defined concept. In $\mathbb{R}^3$, a compact set can be a ball, a disk, a line segment, a Cantor-type set, a snowflake-type fractal curve, or any union of the above. What's the uniform probability measure on those?

But suppose the sets are of positive $n$-dimensional measure, and so normalizing the restriction of this measure gives a probability. Still, the answer is negative: one can make Hausdorff distance arbitrarily small while the cost of transportation will be arbitrarily large. I give an example in one dimension.

Let $A=[-n,n]$ and $$B=[-n,0]\cup \bigcup_{k=1}^m \left[\frac{nk}{m}-\frac{1}{m^2}, \frac{nk}{m}+\frac{1}{m^2}\right]$$ The point being, $B$ has one half of $A$ and some tiny intervals scattered over the other half. They are placed so that $$d_H(A,B)\to 0,\qquad m\to\infty$$ On the other hand, nearly all of mass of $B$ is in $[-n,0]$, so the transportation distance between $\mu_A$ and $\mu_B$ is of order $ n^2$.

$\endgroup$
1
  • $\begingroup$ I meant to specify a positive $n$-dimensional Lebesgue measure. But the rest of your answer resolves the question I meant to ask. $\endgroup$
    – wrvb
    Apr 26, 2016 at 16:56

You must log in to answer this question.

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