A rate of convergence result for a universal D-semifaithful code
- 1 May 1993
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 39 (3) , 813-820
- https://doi.org/10.1109/18.256490
Abstract
The problem of optimal rate universal coding in the context of rate-distortion theory is considered. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to appraoch its lower bound, the rate-distortion function, at a rate O(n-1 log n), and this is conjectured to be optimal based on a result of Pilc. Issues of constructiveness and universality are also addressed.Keywords
This publication has 19 references indexed in Scilit:
- Data compression and histogramsProbability Theory and Related Fields, 1992
- A sequential algorithm for the universal coding of finite memory sourcesIEEE Transactions on Information Theory, 1992
- Density estimation by stochastic complexityIEEE Transactions on Information Theory, 1992
- Minimum complexity density estimationIEEE Transactions on Information Theory, 1991
- Information-theoretic asymptotics of Bayes methodsIEEE Transactions on Information Theory, 1990
- Universal Almost Sure Data CompressionThe Annals of Probability, 1990
- Strong Consistency of the PLS Criterion for Order Determination of Autoregressive ProcessesThe Annals of Statistics, 1989
- Stochastic Complexity and ModelingThe Annals of Statistics, 1986
- Complexity of strings in the class of Markov sourcesIEEE Transactions on Information Theory, 1986
- Minimax noiseless universal coding for Markov sourcesIEEE Transactions on Information Theory, 1983