How to combine distances into a new distance?

Question

What are the general ways of combining two or more distance measures into a new distance measure?

The distances can be easily combined e.g. by taking their linear combination or maximum. I'm looking for ways of combination such that the combined metric is also a distance, i.e. it should satisfy symmetry, triangle inequality and d(x,x) = 0

It seems that the linear combination and the maximum will preserve the above. But what is the most general method for combining distances into a new distance?

Intuitively I would expect $f(d_1(x,y),d_2(x,y))$ where $f$ is (the restriction to the first quadrant of) any norm on $\mathbb R^2$. I can't offhand suggest a proof strategy, though. — hmakholm left over Monica, Sep 04 '17 at 20:20
One way is to mimic the construction of the $p$-norm: let $d(x,y) = (d_1(x,y)^p + d_2(x,y)^p)^{1/p}$. — Ethan Bolker, Sep 04 '17 at 20:21
You can apply any concave function to your metrics as long as it maps 0 to 0 and nothing else to zero. — Ittay Weiss, Sep 04 '17 at 20:24
@EthanBolker does that imply we can just choose $p=1$ and use $d=d_1+d_2$? — it's a hire car baby, May 30 '19 at 18:22
@user334732 Yes, The sum or average or weighted average of metrics is a metric. It's easy to check the axioms. — Ethan Bolker, May 30 '19 at 20:15

score 3 · Accepted Answer · answered Sep 05 '17 at 01:47

What do we need from $f\colon [0,\infty)^2\to [0,\infty)$ in order for $d=f(d_1,d_2)$ to be a metric? Obviously, $f(0,0)=0$ and $f>0$ elsewhere. Then, to have the triangle inequality, we need subadditivity: $$ f(x_1+x_2, y_1+y_2)\le f(x_1, y_1) + f(x_2, y_2) \tag1 $$ combined with monotonicity in each variable: $$ \begin{split} x_1\le x_2 &\implies \forall y\ f(x_1,y)\le f(x_2,y) \\ y_1\le y_2 &\implies \forall x\ f(x,y_1)\le f(x,y_2) \end{split} \tag2$$ Any norm satisfies (1), but not necessarily (2). Property (2) is equivalent to requiring that the projection of the unit disk for the norm on each coordinate axis coincide with its intersection with the axis. A more practical sufficient (though not necessary) condition is that the unit disk is symmetric in each coordinate axis. This is the case for all $\ell^p$ norms, of course.

On the other hand, $f$ need not be a norm; e.g., $f(x,y)=\sqrt{x}+y^{1/3}$ satisfies all the properties too.

Here is a proof that under the above assumptions, $d$ is indeed a metric. It is natural to consider $d_1$ and $d_2$ as metrics on two different metric spaces $X_1,X_2$, being used to define a metric $d$ on the product $X_1\times X_2$. The special case of metrics on the same set is covered by taking $X_1=X_2=X$ and then restricting the metric to the diagonal of the product.

Take any three points $(a_1,a_2)$, $(b_1,b_2)$, $(c_1,c_2)$ in $X_1\times X_2$. Use the triangle inequality, monotonicity, and subadditivity, in that order: $$ \begin{split} d((a_1,a_2), (c_1, c_2)) &= f(d_1(a_1, c_1), d_2(a_2, c_2)) \\ &\le f(d_1(a_1, b_1) + d_1(b_1, c_1) , d_2(a_2, b_2) + d_2(b_2, c_2)) \\ &\le f(d_1(a_1, b_1), d_2(a_2, b_2)) + f( d_1(b_1, c_1) , d_2(b_2, c_2)) \\ & = d((a_1,a_2), (b_1, b_2)) + d((b_1,b_2), (c_1, c_2)) \end{split} $$ as required.

How to combine distances into a new distance?

1 Answers1