UC San Diego

This dissertation addresses the problem of searching a target within a region by sequential

queries with noisy responses. A Bayesian decision maker is responsible to collect observation

samples so as to enhance his knowledge about the true location in a speedy manner. When the

response is noiseless, the classical binary search solves such a problem optimally. Noisy binary search,

on the other hand, has also been formulated and studied extensively in theory over the past 60 years

since Horstein (1963). However, the algorithms developed in noisy binary search problem find

limited practical applications in real-world engineer problem. Motivated by bridging theory and

practice, we formulate the noisy binary search problem by identifying practical scenarios and

constraints that naturally rises with practical applications such as spectrum sensing in cognitive

communication, AoA estimation by adaptive beamforming in large antenna array system, visual

image inspection, bit-wise data transmission, heavy hitter detection in network system, etc.

The first part of the dissertation (Chapter 2) focuses on theoretical understanding and

developing noisy binary search algorithms under those practical constraints. Three algorithms

sortPM, dyaPM, hiePM are proposed. Using the extrinsic Jensen Divergence from information theory, we provide upper bound for the expected search time of each of the algorithms. By

comparing with an information theoretic lower bound, we demonstrate the asymptotic optimality

and suboptimality of the proposed algorithms (asymptotic in the resolution of the target location).

The second part of the dissertation applies the proposed hiePM to practical problems. In

particular, Chapter 3 demonstrates the application of hiePM on the data transmission problem

with noiseless feedback. The dyadic hierarchical query area of hiePM relates directly to the

bit representation of the data stream. This simplifies significantly the corresponding adaptive

encoding scheme and allows a bit-wise encoding. Chapter 4 considers the initial beam alignment

problem in 5G mmWave communication using beamforming. With a single-path channel model,

the problem is reduced to actively searching the Angle-of-Arrival (AoA) of the signal sent from

the user to the Base Station (BS). hiePM is applied to adaptively and sequentially choose the

beamforming from the hierarchical beamforming codebook. The proposed algorithm is compared

to prior works of initial beam alignment that employs linear beam search, repeat binary search,

or random beam search, respectively, and gives the state-of-art performance in terms of both

AoA estimation error at the end of the initial alignment, and the spectral efficiency during the

communication phase.