Searching with measurement dependent noise

Yonatan Kaspi
Postdoctoral researcher, UCSD
Given on: March 6th, 2015


We consider a search problem in which a target is arbitrarily placed on the unit interval. To acquire the target, any region of the interval can be probed for its presence, but the associated measurement noise increases with the size of the probed region. We are interested in the expected search time required to find the target to within some given resolution and error probability. When the measurement noise is constant (independent of the probed region), this problem is known to be equivalent to standard channel coding with feedback. We characterize the optimal tradeoff between time and resolution (i.e., maximal rate), and show that in contrast to the case of constant measurement noise, measurement dependent noise incurs a multiplicative gap between adaptive search and non-adaptive search. Moreover, our adaptive scheme attains the optimal rate-reliability tradeoff. An extension of this problem into a multi-target setting is also considered. We highlight the equivalence of this extension to coding for a certain multiple access channel and the optimal rate, as a function of the number of targets, is characterized. Finally, we show that as the number of targets increases, the performance gap between adaptive- and non-adaptive search becomes negligible. This talk is based on joint work with Ofer Shayevitz and Tara Javidi.


Yonatan Kaspi received the B.Sc, M.Sc and Ph.D degrees from the Technion, Israel Institute of Technology in 2006, 2009, 2013 respectively, all in electrical engineering. Yonatan is the recipient of the Advanced Communication Center (ACC) Feder Family award for outstanding research work in the field of communication technologies (2010) and the Postdoctoral Fellowship of the Information Theory and Applications Center (ITA) at the University of California, San Diego (2013). He is a postdoctoral researcher at ITA since January 2014.