Difference between revisions of "EE662Sp10Semimetric" - Rhea

Revision as of 13:33, 25 March 2010

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)