09/07/2020

Distributed Signal Detection under Communication Constraints

Jayadev Acharya, Clement L Canonne, Himanshu Tyagi

Keywords: Distribution learning/testing, High-dimensional statistics, Information theory

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.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at COLT 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers