| Paper ID | D2-S5-T1.3 |
| Paper Title |
Resolution Limits of Non-Adaptive 20 Questions Estimation for Multiple Targets |
| Authors |
Lin Zhou, Beihang University, China; Alfred Hero, University of Michigan, Ann Arbor, United States |
| Session |
D2-S5-T1: Finite Length Analysis |
| Chaired Session: |
Tuesday, 13 July, 23:20 - 23:40 |
| Engagement Session: |
Tuesday, 13 July, 23:40 - 00:00 |
| Abstract |
We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive the fundamental resolution limit of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_\infty$ norm between the location vector and its estimated version where the maximization is over the possible location vectors of all targets. The fundamental resolution limit is then defined as the minimal achievable resolution of any non-adaptive query procedure. We drive the second-order asymptotic bound on the minimal achievable resolution by relating the current problem to a data transmission problem over a multiple access channel, using the information spectrum by Han and borrowing results from finite blocklength information theory for random access channel coding. Our results refine the purely first-order asymptotic analyses of Kaspi \emph{et al.} (ISIT 2015) for the one-dimensional case. Specifically, we consider more general channels, derive the second-order asymptotic result and establish a phase transition phenomenon.
|
