elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Algorithmic Relative Complexity

Cerra, Daniele and Datcu, Mihai (2011) Algorithmic Relative Complexity. Entropy, 13 (4), pp. 902-914. Multidisciplinary Digital Publishing Institute (MDPI). DOI: 10.3390/e13040902

[img]
Preview
PDF
123kB

Official URL: http://www.mdpi.com/1099-4300/13/4/902/

Abstract

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.

Item URL in elib:https://elib.dlr.de/81121/
Document Type:Article
Title:Algorithmic Relative Complexity
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Cerra, DanieleDLRUNSPECIFIED
Datcu, MihaiDLRUNSPECIFIED
Date:19 April 2011
Journal or Publication Title:Entropy
Refereed publication:Yes
Open Access:Yes
Gold Open Access:Yes
In SCOPUS:Yes
In ISI Web of Science:No
Volume:13
DOI :10.3390/e13040902
Page Range:pp. 902-914
Publisher:Multidisciplinary Digital Publishing Institute (MDPI)
Status:Published
Keywords:Kolmogorov complexity; compression; relative entropy; Kullback-Leibler divergence; similarity measure; compression based distance
HGF - Research field:Aeronautics, Space and Transport (old)
HGF - Program:Space (old)
HGF - Program Themes:W EO - Erdbeobachtung
DLR - Research area:Space
DLR - Program:W EO - Erdbeobachtung
DLR - Research theme (Project):W - Vorhaben hochauflösende Fernerkundungsverfahreen (old)
Location: Oberpfaffenhofen
Institutes and Institutions:Remote Sensing Technology Institute > Photogrammetry and Image Analysis
Deposited By: Cerra, Daniele
Deposited On:18 Feb 2013 13:59
Last Modified:21 Sep 2019 05:05

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.