All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD2-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.