CIF: Small: Poisson matching: A new tool for information theory

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The existence of good designs for communication problems is often demonstrated by studying probability distributions over communication schemes and showing that good ones exist with positive probability. This is called a random coding methodology. The Poisson matching technique to be developed in this project is a novel method of this kind, which has the advantage of working for communication problems with more stringent delay constraints than was previously possible. This is important for emerging modern applications such as the Internet of Things and in scenarios involving control over communication channels, including remote surgery and unmanned vehicles. Because of its ability to work when there are delay constraints, the Poisson matching approach seems particularly promising for discovering better schemes in problems involving multiple agents interacting with each other. Such problems are ubiquitous in networks and have previously resisted attempts to use the earlier available random coding approaches. The goal of this project is to develop the use of the Poisson matching technique in developing good designs for problems of communication, estimation and control involving multiple agents. The Poisson matching lemma can be thought of as a way in which a receiver, having access to a noisy version of a random variable that the sender has access to, can nevertheless coordinate with the sender to pick out the same point from a Poisson process with a probability of error that diminishes as the mutual information increases between the sender and the receiver. This lemma can be used to give very sharp bounds on error probabilities in many of the core one-shot information theory problems - these bounds are usually as good as or better than the previously best known such bounds. At its heart, the Poisson matching lemma is a methodology allowing multiple agents, having related views of some underlying random variable, to coordinate their actions. The project aims to develop the power of the Poisson matching lemma from this more broad perspective, by studying its use in problems of communication, estimation and control involving multiple agents. 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.