Is there a standard measure for how close a matrix is to being a distance metric ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:05:11Z http://mathoverflow.net/feeds/question/30749 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30749/is-there-a-standard-measure-for-how-close-a-matrix-is-to-being-a-distance-metric Is there a standard measure for how close a matrix is to being a distance metric ? Laszlo Kozma 2010-07-06T09:59:30Z 2010-07-06T11:06:01Z <p>Suppose I have a square n*n, symmetric matrix with positive elements and zero diagonal.</p> <p>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).</p> <p>Is there some standard measure that says to what extent this property is violated by a given matrix ?</p> <p>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".</p> http://mathoverflow.net/questions/30749/is-there-a-standard-measure-for-how-close-a-matrix-is-to-being-a-distance-metric/30754#30754 Answer by Suresh Venkat for Is there a standard measure for how close a matrix is to being a distance metric ? Suresh Venkat 2010-07-06T10:36:19Z 2010-07-06T10:36:19Z <p>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. </p> <p>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. </p> <p>It depends on whether you care about "worst-case" or "average-case" behaviour ultimately. </p>