TY - GEN
T1 - Universal coding with point type classes
AU - Iri, Nematollah
AU - Kosut, Oliver
N1 - Funding Information:
This work was supported in part by the National Science Foundation under grant CCF-1422358.
Publisher Copyright:
© 2017 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017/5/10
Y1 - 2017/5/10
N2 - With a customized characterization of types, every universal one-to-one coding algorithm can be described as follows: assign sequences to binary strings based on their type class sizes from smallest to largest. With this view, the universal coding problem is to optimally characterize types. In this paper, this Type Size approach is studied for universal source coding of an exponential family of distributions, using the most natural type class definition: two sequences are in the same type class if and only if they are indistinguishable in the sense that they have the same probability for every distribution in the family. This characterization is called the point type class. Exact third-order coding rate is derived for the resulting compression algorithm, revealing that the point type approach, while natural, is sub-optimal compared to the quantized type method, which was previously proposed by the authors.
AB - With a customized characterization of types, every universal one-to-one coding algorithm can be described as follows: assign sequences to binary strings based on their type class sizes from smallest to largest. With this view, the universal coding problem is to optimally characterize types. In this paper, this Type Size approach is studied for universal source coding of an exponential family of distributions, using the most natural type class definition: two sequences are in the same type class if and only if they are indistinguishable in the sense that they have the same probability for every distribution in the family. This characterization is called the point type class. Exact third-order coding rate is derived for the resulting compression algorithm, revealing that the point type approach, while natural, is sub-optimal compared to the quantized type method, which was previously proposed by the authors.
KW - Data compression
KW - Fine asymptotics
KW - Finite blocklength analysis
KW - Universal algorithm
UR - http://www.scopus.com/inward/record.url?scp=85020207174&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020207174&partnerID=8YFLogxK
U2 - 10.1109/CISS.2017.7926131
DO - 10.1109/CISS.2017.7926131
M3 - Conference contribution
AN - SCOPUS:85020207174
T3 - 2017 51st Annual Conference on Information Sciences and Systems, CISS 2017
BT - 2017 51st Annual Conference on Information Sciences and Systems, CISS 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 51st Annual Conference on Information Sciences and Systems, CISS 2017
Y2 - 22 March 2017 through 24 March 2017
ER -