Fast Beam Alignment for Millimeter Wave Communications: A Sparse Encoding and Phaseless Decoding Approach

In this paper, we study the problem of beam alignment for millimeter wave (mmWave) communications, where a hybrid analog and digital beamforming structure is employed at the transmitter (i.e., base station), and an omni-directional antenna or an antenna array is used at the receiver (i.e., user). By exploiting the sparse scattering nature of mmWave channels, the beam alignment problem is formulated as a sparse encoding and phaseless decoding problem. More specifically, the problem of interest involves finding a sparse sensing matrix and an efficient recovery algorithm to recover the support and magnitude of a sparse signal from compressive phaseless measurements. A sparse bipartite graph code algorithm is developed for sparse encoding and phaseless decoding. Our theoretical analysis shows that, in the noiseless case, our proposed algorithm can perfectly recover the support and magnitude of the sparse signal with a probability exceeding a pre-specified value from O(K2 )  measurements, where K is the number of nonzero entries of the sparse signal. The proposed algorithm has a simple decoding procedure which is computationally efficient and noise robust. Simulation results show that our proposed method renders reliable beam alignment even in the low signal-to-noise ratio regime and presents a clear performance advantage over existing methods.