NDLI: Algorithmic Cross-Complexity and Relative Complexity

Content Provider	IEEE Xplore Digital Library
Author	Cerra, D. Datcu, M.
Copyright Year	2009
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-Leiblerdivergence), 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.
Starting Page	342
Ending Page	351
File Size	328208
Page Count	10
File Format	PDF
ISBN	9781424437535
ISSN	10680314
DOI	10.1109/DCC.2009.6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-03-16
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Information theory Entropy Data compression Mutual information Parallel processing Remote sensing Uncertainty Random variables Approximation algorithms similarity measure Kolmogorov complexity information theory cross-entropy Kullback Leibler divergence algorithmic information theory
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Algorithmic Relative Complexity

A theoretical look at information-driven sensor management criteria

A Similarity Measure Using Smallest Context-Free Grammars

Kullback–Leibler Divergence and Mutual Information of Partitions in Product MV Algebras

Kullback-Leibler Divergence and Mutual Information of Experiments in the Fuzzy Case

GRADE ESTIMATION OF KULLBACK-LEIBLER INFORMATION NeTMBEW BY

Kullback–Leibler Divergence Measure for Multivariate Skew-Normal Distributions

The Cauchy Distribution in Information Theory.

Mutual Information, Metric Entropy, and Cumulative Relative Entropy Risk

Algorithmic Cross-Complexity and Relative Complexity

Similar Documents

Algorithmic Relative Complexity

A theoretical look at information-driven sensor management criteria

A Similarity Measure Using Smallest Context-Free Grammars

Kullback–Leibler Divergence and Mutual Information of Partitions in Product MV Algebras

Kullback-Leibler Divergence and Mutual Information of Experiments in the Fuzzy Case

GRADE ESTIMATION OF KULLBACK-LEIBLER INFORMATION NeTMBEW BY

Kullback–Leibler Divergence Measure for Multivariate Skew-Normal Distributions

The Cauchy Distribution in Information Theory.

Mutual Information, Metric Entropy, and Cumulative Relative Entropy Risk

Algorithmic Cross-Complexity and Relative Complexity