Skip to main content

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

Michelle Effros

Abstract

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

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

Biography

Michelle Effros received the B.S. degree with distinction in 1989, the M.S. degree in 1990, and the Ph.D. degree in 1994, all in electrical
engineering from Stanford University.

During the summers of 1988 and 1989 she worked at Hughes Aircraft Company. She joined the faculty at the California Institute of Technology in 1994 and is currently a Professor of Electrical Engineering. Her research interests include information theory, network coding, data compression, communications, pattern recognition, and image processing.

She received Stanford’s Frederick Emmons Terman Engineering Scholastic Award (for excellence in engineering) in 1989, the Hughes Masters Full-Study Fellowship in 1989, the National Science Foundation Graduate Fellowship in 1990, the AT&T Ph.D. Scholarship in 1993, the NSF CAREER Award in 1995, the Charles Lee Powell Foundation Award in 1997, the Richard Feynman-Hughes Fellowship in 1997, an Okawa Research Grant in 2000, and was cited by Technology Review as one of the world’s top 100 young innovators in 2002.

She is a member of Tau Beta Pi, Phi Beta Kappa, Sigma Xi, and the IEEE Information Theory, Signal Processing, and Communications societies. She served as the Editor of the IEEE Information Theory Society Newsletter from 1995 to 1998 and as a Member of the Board of Governors of the IEEE Information Theory Society from 1998 to 2003. She has served on the IEEE Signal Processing Society Image and Multi-Dimensional Signal Processing (IMDSP) Technical Committee since 2001 and is currently Associate Editor for Source Coding for the IEEE Transactions on Information Theory.

Michelle Effros Headshot
Michelle Effros
California Institute of Technology, Electrical Engineering
EEB 105
23 Feb 2006, 12:00am until 12:00am