Prove identity of indiscernibles

196 Views Asked by At

Define the earth mover's distance as

\begin{equation} EMD(\mathbf{x},\mathbf{y}) = \frac{\sum_{i=1}^m\sum_{j=1}^n f_{ij}d(x_i,y_j)}{\sum_{i=1}^m\sum_{j=1}^n f_{ij}}. \end{equation}

where we define a flow between $\mathbf{x}$ and $\mathbf{y}$ as any matrix of the form $F=(f_{ij}) \in \mathcal{R}^{m \times n}$ and where $d(\cdot)$ is a metric. I'm proving that also EMD is a metric. I have some trouble in proving the identity of indiscernibles, i.e.

$EMD(x,y)=0$ if and only if $x=y$.

I'm in trouble because, if you are familiar with the EMD, if $x=y$ the problem reduces to transport an amount of dirt from itself to itself, which means no transportation at all, so intuitively I think that the flow for any $i,j$ should be equal to zero, but then also $d(\cdot)$ is equal to zero since it is a metric. Does this mean that both the numerator and the denominator are equal to zero? It does not make sense to me, can someone explain how to prove this? Thanks.

1

There are 1 best solutions below

2
On BEST ANSWER

Our flow $(f_{i,j})$ describes how much of the mass at $x_i$ gets transported to $y_j$, e.g. if you don't move the pile of dirt at all would not be the zero matrix, but $f_{i,i}=x_i$ and $f_{i,j} = 0$ if $i\ne j$.

So the zero division cannot occur unless you allow $\bf{x}$ to be the zero vector, which would be nonsensical in this setting.