  Millimeter-wave MIMO systems have gained increasing traction towards the goal
of meeting the high data-rate requirements in next-generation wireless systems.
The focus of this work is on low-complexity beamforming approaches for initial
UE discovery in such systems. Towards this goal, we first note the structure of
the optimal beamformer with per-antenna gain and phase control and the
structure of good beamformers with per-antenna phase-only control. Learning
these beamforming structures in mmW systems is fraught with considerable
complexities such as the need for a non-broadcast system design, the
sensitivity of the beamformer approximants to small path length changes, etc.
To overcome these issues, we establish a physical interpretation between these
beamformer structures and the angles of departure/arrival of the dominant
path(s). This physical interpretation provides a theoretical underpinning to
the emerging interest on directional beamforming approaches that are less
sensitive to small path length changes. While classical approaches for
direction learning such as MUSIC have been well-understood, they suffer from
many practical difficulties in a mmW context such as a non-broadcast system
design and high computational complexity. A simpler broadcast solution for mmW
systems is the adaptation of directional codebooks for beamforming at the two
ends. We establish fundamental limits for the best beam broadening codebooks
and propose a construction motivated by a virtual subarray architecture that is
within a couple of dB of the best tradeoff curve at all useful beam broadening
factors. We finally provide the received SNR loss-UE discovery latency tradeoff
with the proposed constructions. Our results show that users with a reasonable
link margin can be quickly discovered by the proposed design with a smooth
roll-off in performance as the link margin deteriorates.
