This paper considers a target localization problem where at any given time an agent can choose a region to query for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the query region the agent chooses. Motivated by practical applications such as initial beam alignment in array processing, heavy hitter detection in networking, and visual search in robotics, we consider practically important complexity constraints/metrics: time complexity, computational and memory complexity, and the complexity of possible query sets in terms of geometry and cardinality. Two novel search strategy, dyaPM and hiePM, are proposed. Pertinent to the practicality of our solutions, dyaPM and hiePM are of a connected query geometry (i.e. query set is always a connected set) implemented with low computational and memory complexity. Additionally, hiePM has a hierarchical structure and, hence, a further reduction in the cardinality of possible query sets, making hiePM practically suitable for applications such as beamforming in array processing where memory limitations favors a small and predefined query sets. Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence, dyaPM is shown to be asymptotically optimal in search time complexity (asymptotic in both resolution (rate) and error (reliability)). On the other hand, hiePM is shown to be near-optimal in rate. In addition, both hiePM and dyaPM are shown to outperform prior work in the non-asymptotic regime.

Millimeter wave (mmWave) communication with large antenna arrays is a promising technique to enable extremely high data rates due to large available bandwidth in mmWave frequency bands. In addition, given the knowledge of an optimal directional beamforming vector, large antenna arrays have been shown to overcome both the severe signal attenuation in mmWave as well as the interference problem. However, fundamental limits on achievable learning rate of an optimal beamforming vector remain. This paper considers the problem of adaptive and sequential optimization of the beamforming vectors during the initial access phase of communication. With a single-path channel model, the problem is reduced to actively learning the Angle-of-Arrival (AoA) of the signal sent from the user to the Base Station (BS). Drawing on the recent results in the design of a hierarchical beamforming codebook, sequential measurement dependent noisy search strategies, and active learning from an imperfect labeler, an adaptive and sequential alignment algorithm is proposed. For any given resolution and error probability of the estimated AoA, an upper bound on the expected search time of the proposed algorithm is derived via Extrinsic Jensen-Shannon Divergence. The upper bound demonstrates that the search time of the proposed algorithm asymptotically matches the performance of the noiseless bisection search up to a constant factor, in effect, characterizing the AoA acquisition rate. Furthermore, the upper bound shows that the acquired AoA error probability decays exponentially fast with the search time with an exponent that is a decreasing function of the acquisition rate. Numerically, the proposed algorithm is compared with prior work where a significant improvement of the system communication rate is observed. Most notably, in the relevant regime of low (−10 dB to +5 dB) raw SNR, this establishes the first practically viable solution for initial access and, hence, the first demonstration of stand-alone mmWave communication.

This paper considers the problem of bit-wise channel coding over a Binary Symmetric Channel (BSC) with feedback. While it is known that feedback does not increase the capacity of a memoryless channel, it is believed to simplify the coding schemes for some channels. The most significant one is the Binary Erasure Channel (BEC) where capacity is achieved by a simple sequential bit-wise repetition code under which each bit is (re-)transmitted until it is received. This sequential bit-wise feedback code has the added advantage that it can be used for streaming applications over BECs. In contrast, there is no known sequential bit-wise code with feedback that can achieve nonzero transmission rate for a BSC. For example, under Posterior Matching for a binary input channel with feedback, also known as Horstein scheme, each message is considered in its entirety in a block coding manner. This paper proposes a sequential feedback coding scheme with a nested bit-wise structure that generalizes repetition codes. This scheme is shown to achieve strictly positive rate for a large class of binary input channels including a BSC with arbitrary cross-over probability p ∈ (0, 1/2). The analysis relies on characterizing a lower bound on the step-wise Extrinsic Jensen Shannon divergence.

Consider a target search problem on a unit interval where at any given time an agent can choose a region to probe into for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the search region the agent chooses. In this paper, a single-phase sequential and adaptive search algorithm is proposed and shown to achieve the best possible targeting rate and error exponent among all adaptive search algorithms. The proposed algorithm simply adopts a low complexity sorting operation on the posterior of the target and then pick up locations with larger posterior until the probability that the search region contains the target is closest to half.

This paper considers a noncoherent distributed space-frequency coded (SFC) wireless relay system with multiple relays. Each relay adopts a censoring scheme to determine whether the relay will decode and forward the source's information toward the destination. We analytically obtain the achievable diversity for both cases of perfect and imperfect relay censoring. With perfect censoring, we show that the same diversity of a conventional noncoherent SFC MIMO-OFDM system is achievable in the considered noncoherent distributed SFC system with maximum-likelihood (ML) decoding, regardless of whether partial information of channel statistics and relay decoding status is available at the destination. With imperfect censoring, we analytically investigate how censoring errors affect the achievability of the system's diversity. We show that the two types of censoring errors, which correspond to useless and harmful relays, respectively, can decrease the achievable diversity significantly. Our analytical insights and numerical simulations demonstrate that the noncoherent distributed system can offer a comparable diversity as the conventional MIMO-OFDM system if relay censoring is carefully implemented.