1

(Not sure if that is the correct terminology)

Let two metrics on the same domain be defined as isotonic to each other if

$ \left( d_M(x_i,y_i) < d_M(x_j,y_j) \right) \Leftrightarrow \left( d_N(x_i,y_i) < d_N(x_j,y_j) \right)$

For any two pair $(\{x_i,y_i\},\{x_j,y_j\})$. That is, they preserve order of distances between any two pair. Is there a simple test or procedure to determine if the two metrics are isotonic to each other?

A trivial case would be if is a monotonic function of the other ($\|x-y\|_1$ vs $2\|x-y\|_1$), but it may not be that simple. (or the function non-obvious)

Even among strongly equivalent metrics the inequality could fail. Take for instance $L_1$ and $L_2$ norm, and WLOG assume both start at the origin and destination is either $P=(20,15)$ and $Q=(24,10)$. We have $d_1(P)>d_1(Q)$ but $d_2(P)<d_2(Q)$

sheppa28
  • 929

1 Answers1

1

The strategy will depend on the nature of metrics. If the range of $d_M$ is an interval, i.e., it takes on every value between $0$ and the $d_M$-diameter of the space, then in order for $d_N$ to be isotonic to it, it has to be a metric transform of $d_M$, i.e., $d_N=\varphi\circ d_M$ for some increasing $\varphi$. One can get a candidate for $\varphi$ by finding a one-parameter family $(x_t, y_t)$ such that $d_M(x_t, y_t)=t$; for example, $y_t$ might be fixed while $x_t$ moves away from it along a geodesic. Then $\varphi(t) = d_N(x_t, y_t)$, and it remains to check that this $\varphi$ works for all pairs, not just for this family.

Of course, the preceding goes out of the window if the metric space is finite. But then maybe it's feasible to sort $X\times X$ by $(a, b)\preceq (c, d)$ iff $d_M(a, b)\le d_M(c, d)$, and check whether the evaluation of $d_N$ along this sorted set results in monotonically increasing values.

By the way: maps preserving this order relation is sometimes called monotone (although this term is widely used in other ways, too). An example is the paper Monotone maps, sphericity and bounded second eigenvalue.