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

Algorithmic Cross-Complexity and Relative Complexity

Cerra, Daniele and Datcu, Mihai (2009) Algorithmic Cross-Complexity and Relative Complexity. In: IEEE Data Compression Conference, Snowbird, UT, 2009, pp. 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]
Preview
PDF
255kB

Abstract

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.

Item URL in elib:https://elib.dlr.de/58721/
Document Type:Conference or Workshop Item (Paper)
Title:Algorithmic Cross-Complexity and Relative Complexity
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Cerra, DanieleUNSPECIFIEDUNSPECIFIED
Datcu, MihaiUNSPECIFIEDUNSPECIFIED
Date:March 2009
Journal or Publication Title:IEEE Data Compression Conference, Snowbird, UT, 2009
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Page Range:pp. 342-351
Editors:
EditorsEmail
Storer, James A.UNSPECIFIED
Marcelin, Michael W.UNSPECIFIED
Publisher:IEEE Computer Society
ISSN:1068-0314
ISBN:978-0-7695-3592-0
Status:Published
Keywords:Compression, Kolmogorov complexity, algorithmic complexity, Shannon entropy, Kullback Leibler divergence
Event Title:DCC 09 (Data Compression Conference)
Event Location:Snowbird, UT (USA)
Event Type:international Conference
Event Dates:2009-03-18
Organizer:Brandeis University
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 Bildwissenschaften (old)
Location: Oberpfaffenhofen
Institutes and Institutions:Remote Sensing Technology Institute > Photogrammetry and Image Analysis
Deposited By: Cerra, Daniele
Deposited On:23 Apr 2009
Last Modified:31 Jul 2019 19:24

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.