Functional Compression Through Graph Coloring
Authors:
- 12 July 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 56 (8) , 3901-3917
Abstract
Motivated by applications to sensor networks and privacy preserving databases, we consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary but fixed deterministic function of those sources can be computed given the compressed data from each source. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder; 2) under a special condition, lossless computation where both sources are separately encoded; and 3) lossy computation where one source is available at the decoder. For all of these instances, we present a layered architecture for distributed coding: first preprocess data at each source using colorings of certain characteristic graphs and then use standard distributed source coding ( a la Slepian and Wolfs scheme) to compress them. For the first instance, our results extend the approach developed by Orlitsky and Roche (2001) in the sense that our scheme requires simpler structure of coloring rather than independent sets as in the previous case. As an intermediate step to obtain these results, we obtain an asymptotic characterization of conditional graph coloring for an OR product of graphs generalizing a result of Korner (1973), which should be of interest in its own right.Keywords
This publication has 16 references indexed in Scilit:
- On minimum entropy graph colorings2004
- Distributed source coding using syndromes (DISCUS): design and constructionIEEE Transactions on Information Theory, 2003
- On the rate-distortion region for separate encoding of correlated sources2003
- Elements of Information Theory2001
- Source coding and graph entropiesIEEE Transactions on Information Theory, 1996
- Multiterminal source encoding with one distortion criterionIEEE Transactions on Information Theory, 1989
- The zero-error side information problem and chromatic numbers (Corresp.)IEEE Transactions on Information Theory, 1976
- Source coding with side information and a converse for degraded broadcast channelsIEEE Transactions on Information Theory, 1975
- Noiseless coding of correlated information sourcesIEEE Transactions on Information Theory, 1973
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956