On Network Functional Compression
From MaRDI portal
Publication:2986155
DOI10.1109/TIT.2014.2332464zbMATH Open1360.94070arXiv1011.5496WikidataQ111519802 ScholiaQ111519802MaRDI QIDQ2986155FDOQ2986155
Authors: Soheil Feizi, Muriel Médard 
Publication date: 16 May 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: In this paper, we consider different aspects of the network functional compression problem where computation of a function (or, some functions) of sources located at certain nodes in a network is desired at receiver(s). The rate region of this problem has been considered in the literature under certain restrictive assumptions, particularly in terms of the network topology, the functions and the characteristics of the sources. In this paper, we present results that significantly relax these assumptions. Firstly, we consider this problem for an arbitrary tree network and asymptotically lossless computation. We show that, for depth one trees with correlated sources, or for general trees with independent sources, a modularized coding scheme based on graph colorings and Slepian-Wolf compression performs arbitrarily closely to rate lower bounds. For a general tree network with independent sources, optimal computation to be performed at intermediate nodes is derived. We introduce a necessary and sufficient condition on graph colorings of any achievable coding scheme, called coloring connectivity condition (C.C.C.). Secondly, we investigate the effect of having several functions at the receiver. In this problem, we derive a rate region and propose a coding scheme based on graph colorings. Thirdly, we consider the functional compression problem with feedback. We show that, in this problem, unlike Slepian-Wolf compression, by having feedback, one may outperform rate bounds of the case without feedback. Fourthly, we investigate functional computation problem with distortion. We compute a rate-distortion region for this problem. Then, we propose a simple suboptimal coding scheme with a non-trivial performance guarantee. Finally, we introduce cases where finding minimum entropy colorings and therefore, optimal coding schemes can be performed in polynomial time.
Full work available at URL: https://arxiv.org/abs/1011.5496
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)
This page was built for publication: On Network Functional Compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986155)
