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



 Is there a standard measure for how close a matrix is to being a distance metric ?
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. 


