Weighted metric (or semi-metric) with incorporated distance between Dimensions

Question

Im trying to construct a distance Measure between two vectors, that takes into account also the distance between the Dimensions. I will illustrate my Problem with some examples:

$x,y \in \mathbb{R}^n$, $d(x,y)$ fullfills the metric-axioms (but im not shure if the triangle-equality must hold - so a semi-metric could also probably do the job).

1.)

$x_1=1,x_2=1,x_3=1,x_4=1$;

$y_1=0,9;y_2=1,1;y_3=1;y_4=1$;

$d(x,y)=0,1 $

In this example 0.1 is moved from $𝑥_1$ to $𝑦_2$, so the distance between the coordinates is 1, times 0.1 gives $d(x,y)=0.1$.

2.) $x_1=1;x_2=1;x_3=1;x_4=1$;

$y_1=0,9;y_2=1;y_3=1;y_4=1,1$;

$d(x,y)=0.3$

In the second case 0.1 is moved from $x_1$ to $𝑦_4$, so the distance between the coordinates is 3 times 0.1 gives $d(x,y)=0.3$.

3.)

$x_1=2;x_2=2;x_3=2;x_4=2$;

$y_1=1,9;y_2=2,1;y_3=1.9;y_4=2,1;$

$d(x,y)=0.2$

In this example 0.1 is moved from 𝑥1 to 𝑦1 equates to 0.1. Also 0.1 is moved from $𝑥_3$ to $𝑦_4$. In total we moved 0.2 mass from $x_i$ to $x_{i+1}$. Equates to $d(x,y)=0.2$

4.)

$x_1=2;x_2=2;x_3=2;x_4=2$;

$y_1=1,9;y_2=1,8;y_3=2,2;y_4=2,1$;

$d(x,y)=0.5$

In this case either 0.1 is moved from $𝑥_1$ to $𝑦_4$ and 0.2 from $𝑥_2$ to $𝑦_3$. Equates to $d(x,y)=0.3+0.2$. Some more explanations are also possible,i.e: 0.1 is moved from $x_1$ to $y_3$ equals to $d_1(x,y)=0.2$. 0.1 are moved from $x_2$ to $y_3$, $d_2(x,y)=0.1$. 0.1 is moved from $x_2$ to $y_4$, $d_3(x,y)=0.2$. $d(x,y)=d_1+d_2+d_3=0.5.

Im trying to define $d(x,y)$ very general. My first guess was to somehow combine the euclidean distance $\sqrt{(x_i-y_j)^2}$ and the euclidean distance $\sqrt{(i-j)^2}$ but it didnt worked out to well :) I would appreciate any help!

Answer 1

Let $c\colon[n]\times[n]\to\mathbb R$ be any (say transportation cost) function, which may or may not be a metric; here $[n]:=\{1,\dots,n\}$. Then what you apparently want is the Kantorovich--Rubinstein--Wasserstein distance corresponding to the transportation cost function $c$, defined by the formula $$d(x,y):=\min\Big\{\sum_{i,j=1}^n c(i,j)m_{i,j}\,\colon m\in M_{x,y}\Big\}$$ for all $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ in $\mathbb{R}_+^n$, where $M_{x,y}$ is the set of all $n\times n$ matrices $m$ with nonnegative real entries $m_{i,j}$ such that $$\sum_{j=1}^n m_{i,j}=x_i\quad\text{and}\quad \sum_{i=1}^n m_{i,j}=y_j$$ for all $i$ and $j$ in $[n]$.

---

For instance, here is Mathematica's calculation of the ($\ell^1$-)optimal transportation plan for your Example 4) -- which gives the same result, $1/2$, as yours:

We see that it takes Mathematica about 0.014 sec to compute this optimal plan.