Question

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".

Answer 1

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.