Latest revision as of 07:29, 2 April 2010

Not all dissimilarity measures satisfy the triangle inequality...

Numeric Version of Example Given in Lecture

It's easier for me to follow numerical examples than qualitative, so here is the same example Dr. Boutin gave in lecture of a distance function for which the triangle inequality fails to hold reframed in a numeric context.

Let a semimetric $ D $ be defined on $ \mathbb{R}^2 $ as $ D:\mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R} $ by $ (\vec{x_1}, \vec{x_2}) \mapsto d $ where $ d $ is the minimal magnitude non-zero element of the difference vector $ \vec{x_1} - \vec{x_2} $ if such exists or 0 otherwise.

For example, $ D((1, 7), (-3, 12)) = \min\{|4|, |-5|\} = 4 $. $ D((1, 7), (1, 12)) = 5 $. $ D((1, 7), (1, 7)) = 0 $.

Note that the first 3 axioms hold. By definition $ D $ is either 0 or the minimum of the absolute value of non-zero values, hence $ D $ is non-negative. By symmetry of absolute value, $ D $ is symmetric. And $ D $ can only be 0 if the set of non-zero elements of the difference vector is empty, which implies that the vectors are equal. However, consider the following counter-example to the triangle inequality (which is the numerical equivalent of the example given in lecture, where the first component is the level of detail of the image and the second component is the subject of the image).

$ \vec{x_1} = (1, 10), \vec{x_2} = (2, 20), \vec{x_3} = (12, 21) $

Then $ D(\vec{x_1}, \vec{x_2}) = 1, D(\vec{x_2}, \vec{x_3}) = 1, D(\vec{x_1}, \vec{x_3}) = 11 $ and $ 1 + 1 < 11 $.

So the triangle inequality doesn't hold and $ D $ is only a semimetric.

--Jvaught 17:29, 25 March 2010 (UTC)

Back to ECE662 Spring 2010