Distributed Signal Detection under Communication Constraints
Jayadev Acharya, Clement L Canonne, Himanshu Tyagi
Subject areas: Distribution learning/testing, High-dimensional statistics, Information theory
Presented in: Session 4B, Session 4D
[Zoom link for poster in Session 4B], [Zoom link for poster in Session 4D]
Abstract:
Independent draws from a $d$-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has $\ell_2$-norm at least $\varepsilon$, a pre-specified threshold. However, the users can each transmit at most $\ell$ bits to the server. This is a distributed variant of the classic problem of detecting signal in white noise.\n\nWe study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness. We then obtain lower bounds for protocols with public randomness, which are tight when $\ell=O(1)$. We finally conclude with several conjectures and open problems.