On the suboptimality of linear codes for binary distributed hypothesis testing
For information theory, it clarifies the limitations of linear codes in distributed hypothesis testing, showing they cannot achieve optimal error exponents.
The paper studies binary distributed hypothesis testing with linear compression, proving that truncation is optimal among linear codes for certain correlation tests, but that linear codes are strictly suboptimal for testing against independence compared to random coding.
We study a binary distributed hypothesis testing problem where two agents observe correlated binary vectors and communicate compressed information at the same rate to a central decision maker. In particular, we study linear compression schemes and show that simple truncation is the best linear scheme in two cases: (1) testing opposite signs of the same magnitude of correlation, and (2) testing for or against independence. We conjecture, supported by numerical evidence, that truncation is the best linear code for testing any correlations of opposite signs. Further, for testing against independence, we also compute classical random coding exponents and show that truncation, and consequently any linear code, is strictly suboptimal.