A Caltech Library Service

On Approximating the Rate Region for Source Coding with Coded Side Information

Gu, WeiHsin and Effros, Michelle (2007) On Approximating the Rate Region for Source Coding with Coded Side Information. In: Information Theory Workshop (ITW 2007), Tahoe City, CA, 2-6 September 2007. IEEE , Piscataway, NJ, pp. 432-435. ISBN 1-4244-1564-0.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The achievable rate region for the problem of lossless source coding with coded side information was derived by Ahlswede and Körner in 1975. While the Ahlswede-Körner bound completely characterizes the achievable rate region when the source and side information are memoryless, calculating this bound for a given memoryless joint probability mass function on the source and side information requires an optimization over all possible auxiliary random variables meeting a given Markov condition and alphabet size constraint. This optimization turns out to be surprisingly difficult even for very simple distributions on the source and side information. We here propose a (1 + ε)-approximation algorithm for the given rate region. The proposed technique involves quantization of a space of conditional distributions followed by linear programming. The resulting algorithm guarantees performance within a multiplicative factor (1 + ε) of the optimal performance - even when that optimal performance is unknown.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2007 IEEE. Reprinted with permission. Current Version Published: 2007-09-24. This material is based upon work partially supported by NSF Grant No. CCR-0325324 and Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
National Science FoundationCCR-0325324
Lee Center for Advanced Networking, CaltechUNSPECIFIED
Record Number:CaltechAUTHORS:GUWitw07b
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11946
Deposited By: Archive Administrator
Deposited On:13 Oct 2008 21:11
Last Modified:08 Nov 2021 22:23

Repository Staff Only: item control page