Algorithms and Rate-Distortion Bounds in Data Compression for Multi-User Communications

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 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 l22 data clustering.

Parts of the work described in this talk were done in collaboration with Hanying Feng, Dan Muresan, Qian Zhao, and Prof. Leonard Schulman.

http://www.ee2.caltech.edu/Faculty/effros/bio.html