Complexity distortion theory

Complexity distortion theory (CDT) is a mathematical framework providing a unifying perspective on media representation. The key component of this theory is the substitution of the decoder in Shannon's classical communication model with a universal Turing machine. Using this model, the mathemat...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2003-03, Vol.49 (3), p.604-608
Main Authors: Sow, D.M., Eleftheriadis, A.
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic properties
Coding
Communication systems
Complexity
Complexity theory
Decoding
Distortion
Distortion measurement
Ergodic processes
Extraterrestrial measurements
Information systems
Mathematical model
Mathematical models
Rate distortion theory
Rate-distortion
Representations
Source coding
Theory
Turing machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Complexity distortion theory (CDT) is a mathematical framework providing a unifying perspective on media representation. The key component of this theory is the substitution of the decoder in Shannon's classical communication model with a universal Turing machine. Using this model, the mathematical framework for examining the efficiency of coding schemes is the algorithmic or Kolmogorov (1965) complexity. CDT extends this framework to include distortion by defining the complexity distortion function. We show that despite their different natures, CDT and rate distortion theory (RDT) predict asymptotically the same results, under stationary and ergodic assumptions. This closes the circle of representation models, from probabilistic models of information proposed by Shannon in information and rate distortion theories, to deterministic algorithmic models, proposed by Kolmogorov in Kolmogorov complexity theory and its extension to lossy source coding, CDT.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2002.808135