elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Algorithmic Relative Complexity

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

[img]
Vorschau
PDF
123kB

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

Kurzfassung

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.

elib-URL des Eintrags:https://elib.dlr.de/81121/
Dokumentart:Zeitschriftenbeitrag
Titel:Algorithmic Relative Complexity
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Cerra, DanieleDLRNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datcu, MihaiDLRNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:19 April 2011
Erschienen in:Entropy
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Ja
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:13
DOI:10.3390/e13040902
Seitenbereich:Seiten 902-914
Verlag:Multidisciplinary Digital Publishing Institute (MDPI)
Status:veröffentlicht
Stichwörter:Kolmogorov complexity; compression; relative entropy; Kullback-Leibler divergence; similarity measure; compression based distance
HGF - Forschungsbereich:Verkehr und Weltraum (alt)
HGF - Programm:Weltraum (alt)
HGF - Programmthema:W EO - Erdbeobachtung
DLR - Schwerpunkt:Weltraum
DLR - Forschungsgebiet:W EO - Erdbeobachtung
DLR - Teilgebiet (Projekt, Vorhaben):W - Vorhaben hochauflösende Fernerkundungsverfahreen (alt)
Standort: Oberpfaffenhofen
Institute & Einrichtungen:Institut für Methodik der Fernerkundung > Photogrammetrie und Bildanalyse
Hinterlegt von: Cerra, Daniele
Hinterlegt am:18 Feb 2013 13:59
Letzte Änderung:14 Dez 2019 04:20

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.