Kolmogorov complexity vector: A novel data representation

Kolmogorov complexity vector(Kc-vector) stands for a novel compact representation of data from an information theory point of view. In this paper, we define the concept of Kc-vector based on Kolmogorov complexity and information distance. Each coordinate of the Kc-vector represents the information distance between the edges associated with a given vertex and the Kc-vector itself. The term Kc-vector was motivated by eigenvectors due to the similarity and analogy of these two concepts. We show the possibility of computing Kolmogorov complexity vectors directly inspired by the power iteration. We apply the Kc-vector on several domains and find it works robustly well on clustering and ranking. Existing spectral clustering and ranking methods typically require very careful kernel parameter selection and normalization schemes. Here, the Kc-vector we propose is less sensitive to parameter tuning. The compression-based way of Kc-vector computation makes our results invariant to changes on a wide range of kernel parameters or normalization schemes.