Algorithmic relative complexity
type: Item
instance of: scholarly article
title: Algorithmic relative complexity
zbMATH Open document ID: 1229.68046
author: Daniele Cerra
author: Mihai Datcu
published in: Entropy
publication date: 2012-01-09T00:00:00Z
review text: Summary: Information content and compression are tightly related concepts that can be addressed through both classical and algorithmic information theories, on the basis of Shannon entropy and Kolmogorov complexity, respectively. The definition of several entities in Kolmogorov's framework relies upon ideas from classical information theory, and these two approaches share many common traits. In this work, we expand the relations between these two frameworks by introducing algorithmic cross-complexity and relative complexity, counterparts of the cross-entropy and relative entropy (or Kullback-Leibler divergence) found in Shannon's framework. We define the cross-complexity of an object \(x\) with respect to another object \(y\) as the amount of computational resources needed to specify \(x\) in terms of \(y\), and the complexity of \(x\) related to \(y\) as the compression power which is lost when adopting such a description for \(x\), compared to the shortest representation of \(x\). Properties of analogous quantities in classical information theory hold for these new concepts. As these notions are incomputable, a suitable approximation based upon data compression is derived to enable the application to real data, yielding a divergence measure applicable to any pair of strings. Example applications are outlined, involving authorship attribution and satellite image classification, as well as a comparison to similar established techniques.
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 5995950
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: compression
zbMATH Keywords: relative entropy
zbMATH Keywords: Kullback-Leibler divergence
zbMATH Keywords: similarity measure
zbMATH Keywords: compression based distance
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/e13040902
OpenAlex ID: W2095699593
cites work: A Mathematical Theory of Communication
cites work: An introduction to Kolmogorov complexity and its applications
cites work: The Similarity Metric
cites work: A measure of relative entropy between individual sequences with application to universal classification
cites work: A formal theory of inductive inference. Part I
cites work: Three approaches to the quantitative definition of information*
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
cites work: Shared Information and Program Plagiarism Detection
cites work: Clustering by Compression
cites work: On Information and Sufficiency
cites work: Q4457477
cites work: Q3398488
DOI: 10.3390/E13040902
description: scientific article; zbMATH DE number 5995950