Universal Compression, List Decoding, and Logarithmic Loss

Yanina Shkel, Maxim Raginsky, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages206-210
Number of pages5
ISBN (Print)9781538647806
DOIs
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2018-June
ISSN (Print)2157-8095

Other

Other2018 IEEE International Symposium on Information Theory, ISIT 2018
CountryUnited States
CityVail
Period6/17/186/22/18

Fingerprint

List Decoding
Redundancy
Decoding
Logarithmic
Compression
Coding
Constant term
Source Coding
Parameter Uncertainty
Parameter Space
Asymptotic Behavior
Degree of freedom
Optimization Problem
Family

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

Shkel, Y., Raginsky, M., & Verdu, S. (2018). Universal Compression, List Decoding, and Logarithmic Loss. In 2018 IEEE International Symposium on Information Theory, ISIT 2018 (pp. 206-210). [8437892] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2018.8437892

Universal Compression, List Decoding, and Logarithmic Loss. / Shkel, Yanina; Raginsky, Maxim; Verdu, Sergio.

2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 206-210 8437892 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Shkel, Y, Raginsky, M & Verdu, S 2018, Universal Compression, List Decoding, and Logarithmic Loss. in 2018 IEEE International Symposium on Information Theory, ISIT 2018., 8437892, IEEE International Symposium on Information Theory - Proceedings, vol. 2018-June, Institute of Electrical and Electronics Engineers Inc., pp. 206-210, 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 6/17/18. https://doi.org/10.1109/ISIT.2018.8437892
Shkel Y, Raginsky M, Verdu S. Universal Compression, List Decoding, and Logarithmic Loss. In 2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 206-210. 8437892. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2018.8437892
Shkel, Yanina ; Raginsky, Maxim ; Verdu, Sergio. / Universal Compression, List Decoding, and Logarithmic Loss. 2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 206-210 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{30657f1b22a848dfa00efc70a3c4dac3,
title = "Universal Compression, List Decoding, and Logarithmic Loss",
abstract = "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.",
author = "Yanina Shkel and Maxim Raginsky and Sergio Verdu",
year = "2018",
month = "8",
day = "15",
doi = "10.1109/ISIT.2018.8437892",
language = "English (US)",
isbn = "9781538647806",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "206--210",
booktitle = "2018 IEEE International Symposium on Information Theory, ISIT 2018",
address = "United States",

}

TY - GEN

T1 - Universal Compression, List Decoding, and Logarithmic Loss

AU - Shkel, Yanina

AU - Raginsky, Maxim

AU - Verdu, Sergio

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.

ER -