Distributed Functional Compression through Graph Coloring
作者： Vishal Doshi , Devavrat Shah , Muriel Medard , Sidharth Jaggi
DOI: 10.1109/DCC.2007.34
关键词:
摘要: We consider the distributed computation of a function random sources with minimal communication. Specifically, given two discrete memoryless sources, X and Y, receiver wishes to compute f(X, Y) based on (encoded) information sent from Y in manner. A special case, = (X, Y), is classical question source coding considered by Slepian Wolf (1973). Orlitsky Roche (2001) somewhat restricted setup when available as side at receiver. They characterized rate which needs transmit data conditional graph entropy characteristic f. In our recent work (2006), we further established that this can be achieved means coloring (e.g. Slepian-Wolf coding). This characterization allows for separation between "function coding" "correlation coding." paper, more general where are both encoded (separately). significantly harder give single-letter complete region. find under certain condition support set (called zigzag condition), it possible characterize region colorings separately. That is, any achievable pair rates realized first graphs separately (function coding) then using these colors (correlation also obtain joint rate. Finally, provide simulation results establish gains real sequences
computer.org
stanford.edu 
sci-hub.se 参考文章(10)
H. Yamamoto, Wyner - Ziv theory for a general function of the correlated sources (Corresp.) IEEE Transactions on Information Theory. ,vol. 28, pp. 803- 807 ,(1982) , 10.1109/TIT.1982.1056560
H. Witsenhausen, The zero-error side information problem and chromatic numbers (Corresp.) IEEE Transactions on Information Theory. ,vol. 22, pp. 592- 593 ,(1976) , 10.1109/TIT.1976.1055607
Thomas M. Cover, Joy A. Thomas, Elements of information theory ,(1991)
D. Slepian, J. Wolf, Noiseless coding of correlated information sources IEEE Transactions on Information Theory. ,vol. 19, pp. 471- 480 ,(1973) , 10.1109/TIT.1973.1055037
N. Alon, A. Orlitsky, Source coding and graph entropies IEEE Transactions on Information Theory. ,vol. 42, pp. 1329- 1339 ,(1996) , 10.1109/18.532875
R. Cristescu, B. Beferull-Lozano, M. Vetterli, Networked Slepian-Wolf: theory, algorithms, and scaling laws IEEE Transactions on Information Theory. ,vol. 51, pp. 4057- 4073 ,(2005) , 10.1109/TIT.2005.858980
J. Cardinal, S. Fiorini, G. Van Assche, On minimum entropy graph colorings international symposium on information theory. pp. 43- ,(2004) , 10.1109/ISIT.2004.1365077
A. Wyner, J. Ziv, The rate-distortion function for source coding with side information at the decoder IEEE Transactions on Information Theory. ,vol. 22, pp. 1- 10 ,(1976) , 10.1109/TIT.1976.1055508
A. Orlitsky, J.R. Roche, Coding for computing international symposium on information theory. ,vol. 47, pp. 903- 917 ,(1995) , 10.1109/18.915643
Vishal Doshi, Devavrat Shah, Muriel Medard, Sidharth Jaggi, Graph Coloring and Conditional Graph Entropy asilomar conference on signals, systems and computers. pp. 2137- 2141 ,(2006) , 10.1109/ACSSC.2006.355146