Properties of Algorithmic Information Distance

The domain-independent universal Normalized Information Distance based on Kolmogorov complexity has been (in approximate form) successfully applied to a variety of difficult clustering problems. In this paper we investigate theoretical properties of the un-normalized algorithmic information distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{K}$ </tex-math></inline-formula>. The main question we are asking in this work is what properties this curious distance has, besides being a metric. We show that many (in)finite-dimensional spaces can(not) be isometrically scale-embedded into the space of finite strings with metric <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{K}$ </tex-math></inline-formula>. We also show that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{K}$ </tex-math></inline-formula> is not an Euclidean distance, but any finite set of points in Euclidean space can be scale-embedded into <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\{0,1\}^{*},d_{K})$ </tex-math></inline-formula>. A major contribution is the development of the necessary framework and tools for finding more (interesting) properties of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{K}$ </tex-math></inline-formula> in future, and to state several open problems.