0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
2
  • $\begingroup$ Why the downvote? What is wrong with this answer? $\endgroup$ – Iosif Pinelis Jan 17 at 16:12
  • $\begingroup$ Dear Losif, thank you very much! This is really super helpful - and a very elaborated solution to my problem! I cant upvote you, since Im quite new! $\endgroup$ – oyy Jan 18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.