Title :
On approximating the rate regions for lossy source coding with coded and uncoded side information
Author :
WeiHsin Gut ; Jana, Soumya ; Effros, Michelle
Author_Institution :
Deparmment of Electr. Eng., California Inst. of Technol., Pasadena, CA
Abstract :
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.
Keywords :
approximation theory; computational complexity; source coding; Wyner-Ziv problem; algorithmic complexity; approximation algorithm; information theory; linear programming; lossless coding; lossy source coding; lower bound; rate region; uncoded side information; Approximation algorithms; Decoding; Iterative algorithms; Iterative methods; Polynomials; Propagation losses; Random variables; Rate-distortion; Source coding; Transmitters;
Conference_Titel :
Information Theory, 2008. ISIT 2008. IEEE International Symposium on
Conference_Location :
Toronto, ON
Print_ISBN :
978-1-4244-2256-2
Electronic_ISBN :
978-1-4244-2257-9
DOI :
10.1109/ISIT.2008.4595373