CIF: Small: Distributed Function Computation and Multiterminal Data Compression

本文研究了多网络终端对所有观测到的相关数据的共享函数进行高效局部计算的理论和算法设计。终端之间的高效通信促进了高效的计算。应用包括：计算平均值，方差，最大值，最小值和奇偶性的观测数据在一个并列的无线传感器网络，使相关测量。这一目标与为存储和传输目的而有效压缩数据的算法设计以及确保数据安全的算法设计密切相关。该项目的一个主要目标是明确地描述这些连接，从而导致数据压缩，功能计算和网络安全的新的有效算法的发展。技术方法包括使用信息理论框架对潜在问题进行阐述和分析。这将有助于在网络模型中发展“总共享随机性的熵分解”原则，以解决多用户信息理论中的难题，其中高效率函数计算是一个主要例子。特别地，源编码算法在分布式函数计算中的应用将被研究。选择用于研究的开放问题的特定组处理函数计算和数据压缩的一般类型的多终端模型。这种选择是由网络函数计算和源编码以及网络安全的理论和工程实践所激发的，并且具有令人信服的兴趣。

This research addresses the theory and design of algorithms for an efficient local computation by multiple network terminals of shared functions of all their observed correlated data. Efficient communication among the terminals facilitates efficient computation. Applications include: computing the average, variance, maximum, minimum and parity of observed data in a colocated network of wireless sensors that make correlated measurements. This objective is connected closely to the design of algorithms for the efficient compression of data for storage and transmission purposes, as well as of algorithms for assuring data security. A main goal of the project is to characterize explicitly these connections, thereby leading to the development of new and efficient algorithms for data compression, function computation and network security.The technical approach involves a formulation of the underlying problems and their analysis, using an information theoretic framework. This will enable the development of a principle of "entropy decomposition of total shared randomness" in a network model to address difficult problems in multiuser information theory of which rate-efficient function computation is a leading example. In particular, an application of source coding algorithms in distributed function computation will be studied. Specific groups of open problems chosen for investigation address a general class of multiterminal models for function computation and data compression. This choice is motivated by, and is of compelling interest to, the theory and engineering practice of network function computation and source coding, as well as network security.