  Swift and accurate alignment of transmitter (Tx) and receiver (Rx) beams is a
fundamental design challenge to enable reliable outdoor millimeter-wave
communications. In this paper, we propose a new Optimized Two-Stage Search
(OTSS) algorithm for Tx-Rx beam alignment via spatial scanning. In contrast to
one-shot exhaustive search, OTSS judiciously divides the training energy budget
into two stages. In the first stage, OTSS explores and trains all candidate
beam pairs and then eliminates a set of less favorable pairs learned from the
received signal profile. In the second stage, OTSS takes an extra measurement
for each of the survived pairs and combines with the previous measurement to
determine the best one. For OTSS, we derive an upper bound on its misalignment
probability, under a single-path channel model with training codebooks having
an ideal beam pattern. We also characterize the decay rate function of the
upper bound with respect to the training budget and further derive the optimal
design parameters of OTSS that maximize the decay rate. OTSS is proved to
asymptotically outperform state-of-the-art beam alignment algorithms, and is
numerically shown to achieve better performance with limited training budget
and practically synthesized beams.
