TY - GEN

T1 - Universal Compression, List Decoding, and Logarithmic Loss

AU - Shkel, Yanina

AU - Raginsky, Maxim

AU - Verdu, Sergio

N1 - Funding Information:
This work was supported by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370.

PY - 2018/8/15

Y1 - 2018/8/15

N2 - Universal lossy source coding under the logarithmic loss (log-loss) criterion is studied. Bounds on the rate-redundancy of variable-length universal codes with respect to a family of distributions are derived. These bounds correspond to previously derived bounds on distortion-redundancy of fixed-length coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size. As is the case with distortion-redundancy, rate-redundancy of memoryless sources is lower bounded by frac k 2log n, where n is the blocklength and k is the number of degrees of freedom in the parameter space. The impact of the distortion constraint is on the constant term: higher allowed distortion effectively reduces the volume of the parameter uncertainty set. In view of previously established connections between lossy variable-length coding under log-loss and compression with list decoding, the bounds derived in this work also apply to variable-length coding with list decoding.

AB - Universal lossy source coding under the logarithmic loss (log-loss) criterion is studied. Bounds on the rate-redundancy of variable-length universal codes with respect to a family of distributions are derived. These bounds correspond to previously derived bounds on distortion-redundancy of fixed-length coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size. As is the case with distortion-redundancy, rate-redundancy of memoryless sources is lower bounded by frac k 2log n, where n is the blocklength and k is the number of degrees of freedom in the parameter space. The impact of the distortion constraint is on the constant term: higher allowed distortion effectively reduces the volume of the parameter uncertainty set. In view of previously established connections between lossy variable-length coding under log-loss and compression with list decoding, the bounds derived in this work also apply to variable-length coding with list decoding.

UR - http://www.scopus.com/inward/record.url?scp=85052465081&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052465081&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2018.8437892

DO - 10.1109/ISIT.2018.8437892

M3 - Conference contribution

AN - SCOPUS:85052465081

SN - 9781538647806

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 206

EP - 210

BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018

Y2 - 17 June 2018 through 22 June 2018

ER -