Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T02:54:04.193Z Has data issue: false hasContentIssue false

15 - Network Functional Compression

Published online by Cambridge University Press:  22 March 2021

By
Soheil Feizi  and
Muriel Mérd
Edited by
Miguel R. D. Rodrigues  and
Yonina C. Eldar
Miguel R. D. Rodrigues
Affiliation:
University College London
Yonina C. Eldar
Affiliation:
Weizmann Institute of Science, Israel
Get access

Summary

We study compression for function computation of sources at nodes in a network at receiver(s). The rate region of this problem has been considered under restrictive assumptions. We present results that significantly relax these assumptions. For a one-stage tree network, we characterize a rate region by a necessary and sufficient condition for any achievable coloring-based coding scheme, the coloring connectivity condition. We propose a modularized coding scheme based on graph colorings to perform arbitrarily closely to derived rate lower bounds. For a general tree network, we provide a rate lower bound based on graph entropies and show that it is tight for independent sources. We show that, in a general tree network case with independent sources, to achieve the rate lower bound, intermediate nodes should perform computations, but for a family of functions and random variables, which we call chain-rule proper sets, it suffices to have no computations at intermediate nodes to perform arbitrarily closely to the rate lower bound. We consider practicalities of coloring-based coding schemes and propose an efficient algorithm to compute a minimum-entropy coloring of a characteristic graph.

Keywords

compressionnetwork functional compressionnetwork coding
Type
Chapter
Information
Information-Theoretic Methods in Data Science , pp. 455 - 486
Publisher: Cambridge University Press
Print publication year: 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Feizi, S. and Médard, M., “On network functional compression,” IEEE Trans. Information Theory, vol. 60, no. 9, pp. 5387–5401, 2014.CrossRefGoogle Scholar
Kowshik, H. and Kumar, P. R., “Optimal computation of symmetric Boolean functions in tree networks,,” in Proc. 2010 IEEE International Symposium on Information Theory, ISIT 2010, 2010, pp. 1873–1877.Google Scholar
Shenvi, S. and Dey, B. K., “A necessary and sufficient condition for solvability of a 3s/3t sum-network,,” in Proc. 2010 IEEE International Symposium on Information Theory, ISIT 2010, 2010, pp. 1858–1862.Google Scholar
Ramamoorthy, A., “Communicating the sum of sources over a network,,” in Proc. 2008 IEEE International Symposium on Information Theory, ISIT 2008, 2008, pp. 1646–1650.Google Scholar
Gallager, R., “Finding parity in a simple broadcast network,” IEEE Trans. Information Theory, vol. 34, no. 2, pp. 176–180, 1988.Google Scholar
Giridhar, A. and Kumar, P., “Computing and communicating functions over sensor networks,” IEEE J. Selected Areas in Communications, vol. 23, no. 4, pp. 755–764, 2005.Google Scholar
Kamath, S. and Manjunath, D., “On distributed function computation in structure-free random networks,,” in Proc. 2008 IEEE International Symposium on Information Theory, ISIT 2008, 2008, pp. 647–651.Google Scholar
Ma, N., Ishwar, P., and Gupta, P., “Information-theoretic bounds for multiround function computation in collocated networks,” in Proc. 2009 IEEE International Symposium on Information Theory, ISIT 2009, 2009, pp. 2306–2310.Google Scholar
Ahuja, R., Magnanti, T., and Orlin, J., Network flows: Theory, algorithms, and applications. Prentice Hall, 1993.Google Scholar
Shahrokhi, F. and Matula, D., “The maximum concurrent flow problem,” J. ACM, vol. 37, no. 2, pp. 318–334, 1990.Google Scholar
v. Shah, Dey, B., and Manjunath, D., “Network flows for functions,,” in Proc. 2011 IEEE International Symposium on Information Theory, 2011, pp. 234–238.Google Scholar
Bakshi, M. and Effros, M., “On zero-error source coding with feedback,,” in Proc. 2010 IEEE International Symposium on Information Theory, ISIT 2010, 2010.Google Scholar
Kowshik, H. and Kumar, P., “Zero-error function computation in sensor networks,” in Proc. 48th IEEE Conference on Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference, CDC/CCC 2009, 2009, pp. 3787–3792.Google Scholar
Shannon, C. E., “The zero error capacity of a noisy channel,” lRE Trans. lnformation Theory, vol. 2, no. 3, pp. 8–19, 1956.Google Scholar
Orlitsky, A. and Roche, J. R., “Coding for computing,” IEEE Trans. Information Theory, vol. 47, no. 3, pp. 903–917, 2001.CrossRefGoogle Scholar
v. Doshi, Shah, D., Médard, M., and Effros, M., “Functional compression through graph coloring,” IEEE Trans. Information Theory, vol. 56, no. 8, pp. 3901–3917, 2010.Google Scholar
Slepian, D. and Wolf, J. K., “Noiseless coding of correlated Information sources,” IEEE Trans. Information Theory, vol. 19, no. 4, pp. 471–480, 1973.Google Scholar
Pradhan, S. S. and Ramchandran, K., “Distributed source coding using syndromes (DISCUS): Design and construction,” IEEE Trans. Information Theory, vol. 49, no. 3, pp. 626–643, 2003.CrossRefGoogle Scholar
Rimoldi, B. and Urbanke, R., “Asynchronous Slepian–Wolf coding via source-splitting,” in Proc. 1997 IEEE International Symposium on Information Theory, 1997, p. 271.Google Scholar
Coleman, T. P., Lee, A. H., Médard, M., and Effros, M., “Low-complexity approaches to Slepian–Wolf near-lossless distributed data compression,” IEEE Trans. Information Theory, vol. 52, no. 8, pp. 3546–3561, 2006.Google Scholar
Ahlswede, R. F. and Körner, J., “Source coding with side information and a converse for degraded broadcast channels,” IEEE Trans. Information Theory, vol. 21, no. 6, pp. 629–637, 1975.Google Scholar
Körner, J. and Marton, K., “How to encode the modulo-two sum of binary sources,” IEEE Trans. Information Theory, vol. 25, no. 2, pp. 219–221, 1979.Google Scholar
Wyner, A. and Ziv, J., “The rate-distortion function for source coding with side information at the decoder,” IEEE Trans. Information Theory, vol. 22, no. 1, pp. 1–10, 1976.Google Scholar
Yamamoto, H., “Wyner-Ziv theory for a general function of the correlated sources,” IEEE Trans. Information Theory, vol. 28, no. 5, pp. 803–807, 1982.Google Scholar
Feng, H., Effros, M., and Savari, S., “Functional source coding for networks with receiver side information,,” in Proc. Allerton Conference on Communication, Control, and Computing, 2004, pp. 1419–1427.Google Scholar
Berger, T. and Yeung, R. w., “Multiterminal source encoding with one distortion criterion,” IEEE Trans. Information Theory, vol. 35, no. 2, pp. 228–236, 1989.Google Scholar
Barros, J. and Servetto, S., “On the rate-distortion region for separate encoding of correlated sources,,” in IEEE Trans. Information Theory (lSlT), 2003, p. 171.Google Scholar
Wagner, A. B., Tavildar, S., and Viswanath, P., “Rate region of the quadratic Gaussian two-terminal source-coding problem,,” in Proc. 2006 IEEE International Symposium on Information Theory, 2006.Google Scholar
Csiszár, I. and Körner, J., in Information theory: Coding theorems for discrete memoryless systems. New York, 1981.Google Scholar
Witsenhausen, H. S., “The zero-error side information problem and chromatic numbers,” IEEE Trans. Information Theory, vol. 22, no. 5, pp. 592–593, 1976.Google Scholar
Körner, J., “Coding of an information source having ambiguous alphabet and the entropy of graphs,,” in Proc. 6th Prague Conference on Information Theory, 1973, pp. 411–425.Google Scholar
Alon, N. and Orlitsky, A., “Source coding and graph entropies,” IEEE Trans. Information Theory, vol. 42, no. 5, pp. 1329–1339, 1996.Google Scholar
Cardinal, J., Fiorini, S., and Joret, G., “Tight results on minimum entropy set cover,” Algorithmica, vol. 51, no. 1, pp. 49–60, 2008.Google Scholar
Appuswamy, R., Franceschetti, M., Karamchandani, N., and Zeger, K., “Network coding for computing: Cut-set bounds,” IEEE Trans. Information Theory, vol. 57, no. 2, pp. 1015–1030, 2011.Google Scholar
Ahlswede, R., Cai, N., Li, S.-Y. R., and Yeung, R. W., “Network information flow,” IEEE Trans. Information Theory, vol. 46, pp. 1204–1216, 2000.Google Scholar
Koetter, R. and Médard, M., “An algebraic approach to network coding,” IEEE/ACM Trans. Networking, vol. 11, no. 5, pp. 782–795, 2003.Google Scholar
Ho, T., Médard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., and Leong, B., “A random linear network coding approach to multicast,” IEEE Trans. Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×