CUED Publications database

Arbitrary source models and Bayesian codebooks in rate-distortion theory

Kontoyiannis, I and Zhang, J (2002) Arbitrary source models and Bayesian codebooks in rate-distortion theory. IEEE Transactions on Information Theory, 48. pp. 2276-2290. ISSN 0018-9448

Full text not available from this repository.


We characterize the best achievable performance of lossy compression algorithms operating on arbitrary random sources, and with respect to general distortion measures. Direct and converse coding theorems are given for variable-rate codes operating at a fixed distortion level, emphasizing: a) nonasymptotic results, b) optimal or near-optimal redundancy bounds, and c) results with probability one. This development is based in part on the observation that there is a precise correspondence between compression algorithms and probability measures on the reproduction alphabet. This is analogous to the Kraft inequality in lossless data compression. In the case of stationary ergodic sources our results reduce to the classical coding theorems. As an application of these general results, we examine the performance of codes based on mixture codebooks for discrete memoryless sources. A mixture codebook (or Bayesian codebook) is a random codebook generated from a mixture over some class of reproduction distributions. We demonstrate the existence of universal mixture codebooks, and show that it is possible to universally encode memoryless sources with redundancy of approximately (d/2) log n bits, where d is the dimension of the simplex of probability distributions on the reproduction alphabet.

Item Type: Article
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:11
Last Modified: 27 Oct 2020 07:13
DOI: 10.1109/TIT.2002.800493