### 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 language | English (US) |
---|---|

Title of host publication | 2018 IEEE International Symposium on Information Theory, ISIT 2018 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 206-210 |

Number of pages | 5 |

ISBN (Print) | 9781538647806 |

DOIs | |

State | Published - Aug 15 2018 |

Event | 2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States Duration: Jun 17 2018 → Jun 22 2018 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2018-June |

ISSN (Print) | 2157-8095 |

### Other

Other | 2018 IEEE International Symposium on Information Theory, ISIT 2018 |
---|---|

Country | United States |

City | Vail |

Period | 6/17/18 → 6/22/18 |

### Fingerprint

### ASJC Scopus subject areas

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

### Cite this

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -