# Beam Training for Millimeter-Wave Communication Based on Tabu Table Enhanced Rosenbrock Algorithm
## 1 Introduction
### Related Work and Motivation  
The existing beam search algorithms can be classified into three different categories: (1) exhaustive search; (2) hierarchical search [5]; and (3) compressive search [6]. In the exhaustive search scheme, both the transmitter and receiver sequentially scan all the beams to decide the best beam for transmission and reception. As the name suggests, it causes significant training overhead, as the searching times scale linearly with the number of the antenna. As an alternative, the hierarchical search scheme employs two search steps, at the first step, the beam is searched with a low-resolution codebook, based on the coarse direction fund at the first step, a finer search proceeds with a high-resolution codebook. Compared with the exhaustive search scheme, the hierarchical scheme saves much overhead at the cost of coverage loss, which due to the usage of a low-resolution codebook. In the compressive search scheme, the sparse scattering environments of the mm Wave system are considered, and compressive estimation is used to find the best beam. However, the compressive estimation requires the phase coherence across subsequent beacon, which is always difficult to implement [7].  
On the contrary to the approaches assumed in the three schemes above, the beam training process is described as a limited space searching problem in the numerical optimization framework [8]. Modeled a combinatorial optimization of 2-D search space consisting of two pattern indexes from the specified beam codebook, a global direct search (GDS) algorithm is proposed to identify the best transmitter-receiver (Tx-Rx) beam-pair, using the minimum energy to maximize the receiving SNR [9]. In the literature [10], considering that the gradient information of the objective function (i.e., the receiving SNR) is practically unavailable, the Rosenbrock algorithm (RA) is used to carry out beam searching. By a two-step search implicitly approaching the function gradient, this algorithm typically exhibits promising search capabilities. However, when a non-smooth objective function containing many local optima is encountered, the Rosenbrock search may easily fall into local optima, which will cause the search failures. It is noteworthy that the receiving SNRs may exhibit many local optimum values, to overcome the shortcomings of the above classical RA, the literature [11] further proposed to combine RA with simulated annealing (SA) algorithm.  
Although being effective in mitigating the problem of falling into local optimum, it is inevitable for RA that the intermediate search results are round to the integer to get the beam index, which will cause repeated search problems, moreover, considering the clustered structure of beam space immanent to mm Wave, both the correct mapping from beam space to search index, and processing of the index boundary will have a significant impact on the beam search performance. The tabu search (TS) is a kind of heuristic algorithm, which is used in combinatorial optimization problems to obtain the optimum solution. TS is required in many applications to solve optimization problems, including quadratic assignment problems (QAP) [12], detection problems [13], and GFBM systems [14], etc., for their efficiency. The TS algorithm relies on the concept of 'tabu', which prohibits the search of previous searched results to avoid falling into local maximum solution. The concept of 'tabu' motivates us to enhance the RA by TS algorithm.