Algorithms and Rate-Distortion Bounds in Data Compression for Multi-User Communications – Michelle Effros (CalTech)
View Seminar Video
A network source code is a data compression algorithm designed specifically for the multi-user communication system in which it will be employed. Network source codes achieve better rate-distortion trade-offs and improved functionality over the (better known) “point-to-point” source coding alternatives. Perhaps the simplest example of a network source code is the multiresolution code — in which a single transmitter describes the same information to a family of receivers, each of whom receives the data at a different rate; the descriptions are embedded, so that all receivers receive the lowest-rate description, and each higher rate is achieved by adding on to the description at the nearest lower rate. In this talk, I will discuss rate-distortion bounds for lossy network source coding and algorithms for designing codes approaching these bounds. I will focus primarily on a survey of multiresolution source coding results but also include a brief discussion of generalizations to other network source coding environments. Results include rate-distortion bounds, rate-loss bounds, properties of optimal codes, and an approximation algorithm for optimal quantizer design. The quantizer design is based on a new approximation algorithm for $ell_2^2$ data clustering. Parts of the work described in this talk were done in collaboration with Hanying Feng, Dan Muresan, Qian Zhao, and Leonard Schulman.