Hypothesis Testing Over the Two-Hop Relay Network

Sadaf Salehkalaibar, Michèle A. Wigger, Ligong WangIEEE Trans. Information Theory 2019 · OpenReview

TL;DR

This paper introduces novel coding and testing schemes for binary hypothesis testing in a two-hop relay network. It characterizes the achievable error exponents, demonstrating that in specific network configurations, the problem can be decoupled into independent point-to-point tests, simplifying the system and achieving optimal performance.

What Problem Does This Paper Address?

The paper tackles the challenge of distributed hypothesis testing in sensor networks, specifically focusing on a two-hop relay architecture. In such networks, multiple sensors collect correlated data, and this information needs to be processed and transmitted through intermediate relays to a final decision-maker. The core problem is to understand the trade-off between the accuracy of the final decision (quantified by error exponents) and the communication rates available between the terminals. Existing work has primarily focused on simpler network topologies (e.g., one transmitter to one receiver, or one transmitter to multiple receivers). This paper extends the analysis to a more complex two-hop relay scenario, where a transmitter sends information to a relay, which then processes and forwards it to a receiver. This setup is relevant for scenarios like the Internet of Things (IoT) where energy efficiency and limited communication links are crucial.

Methods

The authors propose two main coding and testing schemes for the two-hop relay network. Both schemes utilize cascade source coding techniques, where information is compressed sequentially across the hops. A key component is the unanimous decision-forwarding strategy: a terminal declares the null hypothesis (H=0) only if all preceding terminals have also decided on H=0. Otherwise, it declares the alternative hypothesis (H=1).

The first scheme uses source coding without binning, offering a simpler characterization of achievable error exponents. The second scheme incorporates binning, a technique that can reduce communication rates at the cost of potentially higher error probabilities, leading to a more complex but sometimes superior exponent-rate region.

A significant contribution is the analysis of specific network structures. When the observations form a Markov chain in a particular order (transmitter → relay → receiver), the authors show that the cascade source coding can be decoupled into two independent point-to-point source coding problems. This decoupling simplifies the system design and is shown to be optimal for certain types of hypothesis testing problems ("testing against conditional independence" and some cases of "testing against independence").

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decoupling for Specific Markov Chains: The most striking insight is that for certain network structures (specifically, when observations form a Markov chain X → Y → Z), the complex two-hop problem can be broken down into two independent point-to-point hypothesis testing problems. This is a powerful simplification that can lead to optimal performance.
  • Unanimous Decision-Forwarding: This strategy is crucial for coordinating decisions across the network and ensuring that the final decision is made with high confidence.
  • Binning's Trade-off: The paper highlights that binning can reduce communication rates but introduces competing exponents, making the analysis more intricate.
  • Relay's Role as a Coordinator: In some scenarios, especially when communication rates are constrained, the relay can act as a "coordinator," intelligently processing its own observations and the transmitter's message to improve the receiver's decision accuracy, even reducing the required communication rate.

Key Results

The paper characterizes the achievable type-II error exponents for binary hypothesis testing in the two-hop relay network. They derive explicit expressions for these exponents for the proposed coding schemes.

  • For the X → Y → Z Markov chain case, the proposed schemes achieve optimal type-II error exponents for "testing against conditional independence" and some instances of "testing against independence." The decoupled scheme is shown to be optimal here.
  • For the X → Z → Y Markov chain case, the paper presents optimality results for specific scenarios. It shows that when the relay-to-receiver link rate is sufficiently high, the relay can simply forward the transmitter's message. However, when this rate is low, the relay's own observations become crucial for efficient communication.
  • The paper also provides a detailed analysis of the Shimokawa-Han-Amari binning scheme for the point-to-point case, which serves as a building block for the two-hop analysis.

Limitations and Future Work

  • Weak Converse: The paper focuses on "weak converses," meaning the results hold when type-I error probabilities vanish asymptotically. The authors mention that strong converses (where type-I error probabilities are allowed to be small but non-zero) have been studied for specific cases.
  • Complexity of Binning: While binning offers rate advantages, the resulting exponent characterizations are significantly more complex, involving multiple competing exponents.
  • General Cases: The paper acknowledges that exact solutions for general distributed hypothesis testing problems remain open.
  • Future Work: The authors suggest that further performance improvements might be obtained by binning all codebooks, though this would lead to even more complex exponent expressions. They also point to the need for strong converse proofs for broader applicability.

Summary updated

Abstract

Coding and testing schemes and the corresponding achievable type-II error exponents are presented for binary hypothesis testing over two-hop relay networks. The schemes are based on cascade source coding techniques and unanimous decision-forwarding, the latter meaning that a terminal decides on the null hypothesis only if all previous terminals have decided on the null hypothesis. If the observations at the transmitter, the relay, and the receiver form a Markov chain in this order, then, without loss in performance, the proposed cascade source code can be replaced by two independent point-to-point source codes, one for each hop. The decoupled scheme (combined with decision-forwarding) is shown to attain the optimal type-II error exponents for various instances of “testing against conditional independence.” The same decoupling is shown to be optimal also for some instances of “testing against independence,” when the observations at the transmitter, the receiver, and the relay form a Markov chain in this order and when the relay-to-receiver link is of sufficiently high rate. For completeness, this paper also presents an analysis of the Shimokawa-Han-Amari binning scheme for the point-to-point hypothesis testing setup.
BibTeX
@article{salehkalaibar2019hypothesis,
  author = {Sadaf Salehkalaibar and Michèle A. Wigger and Ligong Wang},
  title = {{Hypothesis Testing Over the Two-Hop Relay Network}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=UAXppKspEFB},
}
Figure