Events Calendar

Lossy Data Compression: Non-asymptotic Fundamental Limits

Speaker: Victoria Kostina, Princeton University

Talk Title: Lossy Data Compression: Non-asymptotic Fundamental Limits

Abstract: The basic tradeoff in lossy compression is that between the compression ratio (rate) and the fidelity of reproduction of the object that is compressed. Traditional (asymptotic) information theory seeks to describe the optimum tradeoff between rate and fidelity achievable in the limit of infinite length of the source block to be compressed. A perennial question in information theory is how relevant the asymptotic fundamental limits are when the communication system is forced to operate at a given, fixed blocklength. The finite blocklength (delay) constraint is inherent to all communication scenarios. In fact, in many systems of current interest, such as real-time multimedia communication, delays are strictly constrained, while in packetized data communication, packets are frequently on the order of 1000 bits.

Motivated by critical practical interest in non-asymptotic information-theoretic limits, we study the optimum rate-fidelity tradeoffs in lossy source coding and joint source-channel coding at a given fixed blocklength. While computable formulas for the asymptotic fundamental limits are available for a wide class of channels and sources, the luxury of being able to compute exactly (in polynomial time) non-asymptotic fundamental limits is rarely affordable. One can at most hope to obtain bounds and approximations to information-theoretic non-asymptotic fundamental limits. Our main findings include tight bounds to the non-asymptotic fundamental limits in lossy data compression and transmission, valid for general sources without any assumptions on ergodicity or memorylessness. Moreover, in the stationary memoryless case we show a simple formula approximating the non-asymptotic optimal coding rate that involves only two parameters of the source.


Biography: Victoria Kostina received the Bachelors degree with honors in applied mathematics and physics from the Moscow Institute of Physics and Technology, Russia, in 2004, where she was affiliated with the Institute for Information Transmission Problems of the Russian Academy of Sciences, and the Masters degree in electrical engineering from the University of Ottawa, Canada, in 2006. In September 2013, she completed her Ph.D. in electrical engineering at Princeton University, and is currently a postdoctoral researcher working with Prof. Sergio Verdú. Her research interests lie in information theory, theory of random processes, coding, and wireless communications. She is the recipient of two Natural Sciences and Engineering Research Council of Canada postgraduate fellowships, the Upton Fellowship in Engineering from Princeton University, the University of Ottawa Excellence Scholarship, the University of Ottawa Admission Scholarship and the Moscow Institute of Physics and Technology Excellence Scholarship.

Host: Urbashi Mitra, ubli@usc.edu, EEB 540, x04667

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Susan Wiedem