CIF: Small: Shared Information: Theory and Applications

University Of Maryland, College Park, College Park MD

Investigators

Abstract

This research develops the concept of shared information as a fundamental, quantifiable, and compact measure for capturing interdependence among multiple correlated signals. It will seek to emulate and enhance the spirit of Claude Shannon’s celebrated and enormously consequential notion of mutual information which constitutes a measure of correlation between two random signals. The role of shared information will be investigated for operational meanings in network information theory with implications for related communication applications and as a self-contained, compact, and calculable figure-of-merit that can be optimized in learning applications where statistical correlation is of central interest. The goal is to establish central theoretical and practical roles for shared information in network data compression, distributed function computation, reliable and secure information transmission in networks, signal cluster detection, and a new category of statistical estimation and learning algorithms. Engineering applications include communication and signal processing in a smart home, satellite image reconstruction, and messaging protocols in automated guided vehicles and drone swarms. The technical approach involves (i) establishing basic properties of shared information; (ii) examining its role in common randomness generation including algorithms for combinatorial tree packing and network function computation, especially signal acquisition or omniscience; (iii) querying common randomness; (iv) hypothesis testing for cluster and community detection; (v) multiuser data compression and channel transmission; and (vi) estimation of shared information when the underlying probability distribution of the signals is unknown. Rooted in information theory, the research has rich connections to algorithms in combinatorial graph theory (in Theoretical Computer Science) and correlated multiarmed bandits (in Learning). It aims to create advances in network information theory through new models and methods that highlight interactive communication among the terminals, with the concept of shared information serving as a linchpin. Links to important problems in combinatorial algorithms, by way of shared information, highlight interpretations that promise new understanding and solutions. Furthermore, the estimation of shared information using correlated multiarmed bandits will introduce models, concepts, and algorithms in an essential but fledgling realm of machine learning. The research will be accomplished using methods from information theory, Markov random fields, combinatorial graph theory, and statistical inference. Expected research outcomes include interactive techniques for multiuser data compression and channel transmission, algorithms for combinatorial tree packing, methods for detecting clusters of correlated signals, and bandit algorithms for parameter estimation in correlated signals. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.