Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- Contributors
- 1 Introduction to Information Theory and Data Science.
- 2 An Information-Theoretic Approach to Analog-to-Digital Compression
- 3 Compressed Sensing via Compression Codes
- 4 Information-Theoretic Bounds on Sketching
- 5 Sample Complexity Bounds for Dictionary Learning from Vector- and Tensor-Valued Data
- 6 Uncertainty Relations and Sparse Signal Recovery
- 7 Understanding Phase Transitions via Mutual Information and MMSE
- 8 Computing Choice: Learning Distributions over Permutations
- 9 Universal Clustering
- 10 Information-Theoretic Stability and Generalization
- 11 Information Bottleneck and Representation Learning
- 12 Fundamental Limits in Model Selection for Modern Data Analysis
- 13 Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
- 14 Distributed Statistical Inference with Compressed Data
- 15 Network Functional Compression
- 16 An Introductory Guide to Fano’s Inequality with Applications in Statistical Estimation
- Index
- References
15 - Network Functional Compression
Published online by Cambridge University Press: 22 March 2021
Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- Contributors
- 1 Introduction to Information Theory and Data Science.
- 2 An Information-Theoretic Approach to Analog-to-Digital Compression
- 3 Compressed Sensing via Compression Codes
- 4 Information-Theoretic Bounds on Sketching
- 5 Sample Complexity Bounds for Dictionary Learning from Vector- and Tensor-Valued Data
- 6 Uncertainty Relations and Sparse Signal Recovery
- 7 Understanding Phase Transitions via Mutual Information and MMSE
- 8 Computing Choice: Learning Distributions over Permutations
- 9 Universal Clustering
- 10 Information-Theoretic Stability and Generalization
- 11 Information Bottleneck and Representation Learning
- 12 Fundamental Limits in Model Selection for Modern Data Analysis
- 13 Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
- 14 Distributed Statistical Inference with Compressed Data
- 15 Network Functional Compression
- 16 An Introductory Guide to Fano’s Inequality with Applications in Statistical Estimation
- Index
- References
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.
- Type
- Chapter
- Information
- Information-Theoretic Methods in Data Science , pp. 455 - 486Publisher: Cambridge University PressPrint publication year: 2021
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