Millimeter-Wave (mm-Wave) frequency bands provide an opportunity for much wider channel bandwidth compared with the traditional sub-6 GHz band. Communication at mm-Waves is, however, quite challenging due to the severe propagation path loss. To cope with this problem, directional beamforming both at the Base Station (BS) side and at the user side is necessary in order to establish a strong path conveying enough signal power. Finding such beamforming directions is referred to as the Beam Alignment (BA) and is known to be a challenging problem. This paper presents a new scheme for efficient BA, based on the estimated second order channel statistics. As a result, our proposed algorithm is highly robust to variations of the channel time-dynamics compared with other proposed approaches based on the estimation of the channel coefficients, rather than of their second-order statistics. In the proposed scheme, the BS probes the channel in the Downlink (DL) letting each user to estimate its own path direction. All the users within the BS coverage are trained simultaneously, without requiring "beam refinement" with multiple interactive rounds of Downlink/Uplink (DL/UL) transmissions, as done in other schemes. Thus, the training overhead of the proposed BA scheme is independent of the number of users in the system. We pose the channel estimation at the user side as a Compressed Sensing (CS) of a non-negative signal and use the recently developed Non-Negative Least Squares(NNLS) technique to solve it efficiently. The performance of our proposed algorithm is assessed via computer simulation in a relevant mm-Wave scenario. The results illustrate that our approach is superior to the state-of-the-art BA schemes proposed in the literature in terms of training overhead in multi-user scenarios and robustness to variations in the channel dynamics.