An old coding theorem (and a few new ones, too)

Thomas Courtade
Assistant Professor, UC Berkeley
Given on: Nov. 7th, 2014

Abstract

In 1965, L.L. Campbell discovered a beautiful connection between Rényi entropy and the exponential moments of codeword lengths in lossless compression. While Campbell's theorem is unfamiliar to most, it has a natural place in the now-fashionable `one-shot’ approach that has proved central to non-asymptotic analyses of the three major Shannon-theoretic settings: lossless compression, lossy compression, and data transmission.

In this talk, I will show that Campbell’s result was a precursor to the one-shot paradigm. Indeed, it contains all the information-theoretic ingredients necessary to prove non-asymptotic lossless compression theorems in full generality by only invoking standard limiting arguments. I will also discuss analogs of Campbell’s coding theorem for lossy compression and data transmission in terms of the d-tilted Rényi entropy and the Rényi mutual information, respectively.

This is joint work with Sergio Verdú.

Bio

Thomas Courtade is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences. Before joining Berkeley in 2014, he was at Stanford University, where he was supported by a postdoctoral fellowship through the NSF Center for Science of Information. He graduated summa cum laude with a B.Sc. in Electrical Engineering from Michigan Technological University in 2007, and received his M.Sc. and Ph.D. degrees in Electrical Engineering from UCLA in 2008 and 2012, respectively.