|
Title:
|
Faster Sequential Universal Coding via Block Partitioning |
|
Author:
|
Baron, Dror; Baraniuk, Richard G.
|
|
Type:
|
Journal Paper |
|
Keywords:
|
Lossless source coding; redundancy; sequential coding; universal coding |
|
Citation:
|
D. Baron and R. G. Baraniuk, "Faster Sequential Universal Coding via Block Partitioning," IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1708-1710, 2006. |
|
Abstract:
|
Rissanen provided a sequential universal coding algorithm based on a block partitioning scheme, where the source model is estimated at the beginning of each block. This approach asymptotically approaches the entropy at the fastest possible rate of 1/2log(n) bits per unknown parameter. We show that the complexity of this algorithm is /spl Omega/(nlog(n)), which is comparable to existing sequential universal algorithms. We provide a sequential O(nlog(log(n))) algorithm by modifying Rissanen's block partitioning scheme. The redundancy with our approach is greater than with Rissanen's block partitioning scheme by a multiplicative factor 1+O(1/log(log(n))), hence it asymptotically approaches the entropy at the fastest possible rate. |
|
Date Published:
|
2006-04-01 |
