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?

  • $\begingroup$ 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. $\endgroup$ Sep 4 '17 at 20:20
  • 3
    $\begingroup$ 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}$. $\endgroup$ Sep 4 '17 at 20:21
  • $\begingroup$ You can apply any concave function to your metrics as long as it maps 0 to 0 and nothing else to zero. $\endgroup$ Sep 4 '17 at 20:24
  • $\begingroup$ @EthanBolker does that imply we can just choose $p=1$ and use $d=d_1+d_2$? $\endgroup$ May 30 '19 at 18:22
  • 1
    $\begingroup$ @user334732 Yes, The sum or average or weighted average of metrics is a metric. It's easy to check the axioms. $\endgroup$ May 30 '19 at 20:15

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.


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.