Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.