Efficient Resource Allocation Schemes for Search.

This thesis concerns the problem of efficient resourceallocation under constraints. In many applications a finitebudget is used and allocating it efficiently can improveperformance. In the context of medical imaging the constraint is exposure to ionizing radiation, e.g., computed tomography (CT). In radar and target tracking time spent searching a particular region before pointing the radar to another location or transmitted energy level may be limited. In airport security screening the constraint is screeners' time. This work addresses both static and dynamic resource allocation policies where the question is: How a budget should be allocated to maximize a certain performance criterion.In addition, many of the above examples correspond to aneedle-in-a-haystack scenario. The goal is to find a smallnumber of details, namely `targets', spread out in a fargreater domain. The set of `targets' is named a region ofinterest (ROI). For example, in airport security screeningperhaps one in a hundred travelers carry prohibited item and maybe one in several millions is a terrorist or a real threat. Nevertheless, in most aforementioned applications the common resource allocation policy is exhaustive: all possible locations are searched with equal effort allocation to spread sensitivity.A novel framework to deal with the problem of efficientresource allocation is introduced. The framework consists of a cost function trading the proportion of efforts allocated to the ROI and to its complement. Optimal resource allocation policies minimizing the cost are derived. These policies result in superior estimation and detection performance compared to an exhaustive resource allocation policy. Moreover, minimizing the cost has a strong connection to minimizing both probability of error and the CR bound on estimation mean square error. Furthermore, it is shown that the allocation policiesasymptotically converge to the omniscient allocation policythat knows the location of the ROI in advance. Finally, amulti-scale allocation policy suitable for scenarios wheretargets tend to cluster is introduced. For a sparse scenario exhibiting good contrast between targets and background this method achieves significant performance gain yet tremendously reduces the number of samples required compared to an exhaustive search.