Suppose I have a square n*n, symmetric matrix with positive elements and zero diagonal.

For this to be considered a proper distance metric between n points, the triangle inequality needs to be satisfied (the other requirements follow from the definition).

Is there some standard measure that says to what extent this property is violated by a given matrix ?

In particular, is there a measure that is fast to compute and can such a thing be optimized for ? I.e. obtain solution X that is "as close to being a metric as possible".


There are a couple of plausible measures you could employ. One would be to minimize the Frobenius distance between the given matrix (call it $D$) and the target matrix $X$ . Since the space of all distance matrices that satisfy triangle inequality can be expressed using linear constraints, you end up with a least-squares problem that can be solved optimally.

Another measure that's more popular in the theoryCS community would be to find a matrix satisfying the triangle inequality where the worst-case ratio (the distortion) of distances was minimized. You could write this as "minimize $\lambda$ where $(1/\lambda)d_{ij} \le x_{ij} \le \lambda d_{ij}$ for all (i,j) pairs", and again write the linear constraints ensuring that $X$ satisfies triangle inequality. this is a linear program.

It depends on whether you care about "worst-case" or "average-case" behaviour ultimately.

| cite | improve this answer | |

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.