On approximating the rate regions for lossy source coding with coded and uncoded side information

We derive new algorithms for approximating the rate regions for a family of source coding problems that includes lossy source coding, lossy source coding with uncoded side information at the receiver (the Wyner-Ziv problem), and an achievability bound for lossy source coding with coded side in formation at the receiver. The new algorithms generalize a recent approximation algorithm by Go and Effros from lossless to lossy coding. In each case, prior information theoretic descriptions of the desired regions are available but difficult to evaluate for example sources due to their dependence on auxiliary random variables. Our algorithm builds a linear program whose solution is no less than the desired lower bound and no greater than (1 + isin) times that optimal value. These guarantees are met even when the optimal value is unknown. Here isin > 0 is a parameter chosen by the user; the algorithmic complexity grows as O(isin^-M) as e approaches 0, where M > 4 is a constant that depends on the source coding problem and the alphabet sizes of the sources.