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

Algorithmic Cross-Complexity and Relative Complexity

Cerra, Daniele und Datcu, Mihai (2009) Algorithmic Cross-Complexity and Relative Complexity. In: IEEE Data Compression Conference, Snowbird, UT, 2009, Seiten 342-351. IEEE Computer Society. DCC 09 (Data Compression Conference), 2009-03-18, Snowbird, UT (USA). ISBN 978-0-7695-3592-0. ISSN 1068-0314.

[img]
Vorschau
PDF
255kB

Kurzfassung

Information content and compression are tightly related concepts that can be addressed by classical and algorithmic information theory. Several entities in the latter have been defined relying upon notions of the former, such as entropy and mutual information, since the basic concepts of these two approaches present many common tracts. In this work we further expand this parallelism by defining the algorithmic versions of cross-entropy and relative entropy (or Kullback-Leibler divergence), two well-known concepts in classical information theory. 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 using such a description for x, with respect to its shortest representation. Since the main drawback of these concepts is their uncomputability, a suitable approximation based on data compression is derived for both and applied to real data. This allows us to improve the results obtained by similar previous methods which were intuitively defined.

elib-URL des Eintrags:https://elib.dlr.de/58721/
Dokumentart:Konferenzbeitrag (Paper)
Titel:Algorithmic Cross-Complexity and Relative Complexity
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Cerra, DanieleNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datcu, MihaiNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:März 2009
Erschienen in:IEEE Data Compression Conference, Snowbird, UT, 2009
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Nein
In ISI Web of Science:Nein
Seitenbereich:Seiten 342-351
Herausgeber:
HerausgeberInstitution und/oder E-Mail-Adresse der HerausgeberHerausgeber-ORCID-iDORCID Put Code
Storer, James A.NICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Marcelin, Michael W.NICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Verlag:IEEE Computer Society
ISSN:1068-0314
ISBN:978-0-7695-3592-0
Status:veröffentlicht
Stichwörter:Compression, Kolmogorov complexity, algorithmic complexity, Shannon entropy, Kullback Leibler divergence
Veranstaltungstitel:DCC 09 (Data Compression Conference)
Veranstaltungsort:Snowbird, UT (USA)
Veranstaltungsart:internationale Konferenz
Veranstaltungsdatum:18 März 2009
Veranstalter :Brandeis University
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 Bildwissenschaften (alt)
Standort: Oberpfaffenhofen
Institute & Einrichtungen:Institut für Methodik der Fernerkundung > Photogrammetrie und Bildanalyse
Hinterlegt von: Cerra, Daniele
Hinterlegt am:23 Apr 2009
Letzte Änderung:24 Apr 2024 19:23

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.