Non-asymptotics in Information Theory

February 15, 2013, Webb 1100

Sergio Verdú

Princeton University, Electrical Engineering


Traditional results on the fundamental limits of data compression and data transmission through noisy channels apply to the asymptotic regime as delay (or blocklength) goes to infinity. In this talk, I review our recent progress on the analysis of the fundamental limits as a function of blocklength, motivated by modern applications in which limited delay is a key design constraint. Going beyond traditional refinements to the fundamental asymptotic information theoretic limits, we investigate the backoff from capacity (in channel coding) and the overhead over entropy (in lossless compression) and the rate-distortion function (in lossy source coding) incurred by coding at a given blocklength. Requiring new proof techniques our approach has dual components:  computable upper/lower bounds tight enough to reduce the uncertainty on the non-asymptotic fundamental limit to a level that is negligible compared to the gap to the long-blocklength asymptotics; and analytical approximations to the bounds that are accurate even for short blocklengths. 

Speaker's Bio

Sergio Verdú has been on the Faculty of Princeton University since 1984.
He teaches and conducts research in the Department of Electrical Engineering of the School of Engineering and Applied Science. A member of the Information Sciences and Systems group and the Program in Applied and Computational Mathematics, his research interests are in Information Theory, Data Compression and Transmission.