Complexity Distortion Theory

Daby Sow and Alexandros Eleftheriadis
Department of Electrical Engineering, Columbia University

Proceedings, IEEE International Symposium on Information Theory and its Applications, Ulm, Germany, June-July 1997.

Abstract

We investigate the efficiency of lossy algorithmic representations of information and show that "Complexity Distortion" is assymptotically equivalent to Rate Distortion for stationary ergodic sources.

PostScript (19 KB)