Distributed hypothesis testing via equivalence to channel coding

Yuval Kochman

School of Computer Science and Engineering at the Hebrew University of Jerusalem

Abstract:

We consider the problem of distributed binary hypothesis testing of a pair of sequences. We will mostly follow the illustrative example where the sequences are generated by a doubly symmetric binary source with one of two possible crossover probabilities. The sequences are observed by two terminals, which communicate with a decision function via rate-limited links; we are interested in the optimal tradeoff between the error exponents of the testing problem, for a given pair of communication rates.

We first consider the side-information setting where one terminal is allowed to send the full sequence. We show that the problem is equivalent to one of "channel detection". We further analyze a suboptimal scheme based on Wyner-Ziv coding; interestingly, for such a scheme a binning error event does not necessarily lead to an erroneous decision upon the hypothesis. By carefully analyzing the error events, we are able to give achievability results that are better and more comprehensive than previously known.

We then turn to the setting of symmetric rates. We use structured binning (a Korner-Marton approach) to obtain achievable error exponents, that demonstrate no degradation with respect to the side-information setting with the same rate.

Based on joint works with Eli Haim and Nir Weinberger (Tel Aviv University)

Biography:

Yuval Kochman received his B.Sc. (cum laude), M.Sc. (cum laude) and Ph.D. degrees from Tel Aviv University in 1993, 2003 and 2010, respectively, all in electrical engineering. During 2009–2011, he was a Postdoctoral Associate at the Signals, Information and Algorithms Laboratory at the Massachusetts Institute of Technology (MIT), Cambridge, MA, USA. Since 2012, he has been with the School of Computer Science and Engineering at the Hebrew University of Jerusalem. Outside academia, he has worked in the areas of radar and digital communications. His research interests include information theory, communications and signal processing.