EE Systems Seminar

Abstract: Information acquisition problems form a class of stochastic control and decision problems in which a decision maker is faced with utilizing a stochastically varying (and uncontrollable) environment whose state is only partially observable to the decision maker. To best utilize the system, our decision maker can carefully control the acquisition process via which the set of (noisy) measurements are collected. Our overall research objective has been to characterize the fundamental (information theoretic) limits and gains associated with dynamically controlling the acquisition process.

In this talk, we focus on the special case of measurement-dependent noisy search; this problem arises in a broad spectrum of applications such as medical diagnosis, spectrum sensing, sensor management, initial access in mmWave communication, and noisy group testing. In this set up, the decision maker is tasked with locating a (collection of) stationary point target(s) in a compact interval by selecting and inspecting a sequence of subregions. We are interested in the expected search time required to find the target(s) to within some given resolution and error probability (reliability). Motivated by real world scenarios, we assume that the outcome of inspecting any subregion is subject to an additive noise whose distribution (and hence variance) depends strongly on (increases with) the size of the inspection subregion. We provide a non-asymptotic characterization of the optimal tradeoff between search time, resolution, and search reliability and show that there is a multiplicative (non-asymptotic) gap between adaptive search and non-adaptive search strategies when the noise statistics are functions of inspection region.  We also highlight the  implication of our finding in various asymptotic regimes. Our framework rests upon reframing the contributions due to Wald, Blackwell, and DeGroot and identifying the missing link of information acquisition rate in Chernoff's seminal work on active hypothesis testing. Our analysis is sequential in nature and connects De Groot's notion of information utility with the Shannon theoretic concept of uncertainty reduction to introduce an appropriate symmetrized divergence measure: Extrinsic Jensen-Shannon (EJS) divergence.  Our achievability scheme, i.e. the optimal (adaptive) search strategy, generalizes the Posterior Matching of Shayevitz and Feder for channel coding with feedback.

We will end the talk by going back to the original setting and briefly mention the implication of our work for the following application areas of interest: Machine-integrate Inverse Problems, Active Learning, Distributed Social Learning, and Adaptive Object Detection in Computer Vision.
This work was done in collaborations with my PhD students S. Chiu and M. Naghshvar, as well as Y. Kaspi, O. Shayevitz, and M. Wigger.

Bio: Tara Javidi did her undergraduate studies at Sharif University of Technology, Tehran, Iran from 1992 to 1996. From 1996 to 2002, she was a graduate student of electrical engineering as well as applied mathematics at the University of Michigan, Ann Arbor. From 2002 to 2004, Tara was an assistant professor of the electrical engineering at the University of Washington, Seattle. In 2005, she joined the University of California, San Diego, where she is currently a professor of electrical and computer engineering.

Host: Victoria Kostina