# Early Neighbor Rejection-Aided Tabu Search Detection for Large MIMO Systems
## 3 Proposed Low Complexity TS Algorithms
### ENR-QR-TS with Layer Ordering  
In the proposed ENR-QR-TS scheme, we exclude \(k\) neighbors associated with the largest cumulative metrics in each layer. If in the first layer, the cumulative metric of the best neighbor is larger than those of the other neighbors, it is excluded early by the ENR scheme, which leads to the selection of the wrong best neighbor. To avoid this undesired consequence, we should minimize the mismatch between the complete metric and cumulative metrics in early layers.  
The expected metric of the \(i\)th layer can be rewritten as in [12], as  
\[\mathbb{E}\Big{\{}|z_{i}+r_{i,d}\delta_{d}|^{2}\Big{\}}\approx\sigma_{n}^{2}+| r_{i,d}|^{2}\delta^{2}, \tag{15}\]  
where \(\sigma_{n}^{2}\) is a constant and \(\delta^{2}=|\delta_{d}|^{2}\). In (15), it can be seen that the expected metric at layer \(i\) depends only on \(|r_{i,d}|^{2}\). Furthermore, as \(|r_{i,d}|^{2}\) is larger, the expected metric of the \(i\)th layer is larger, which contributes more significantly to the complete metric. Therefore, to minimize the mismatch between the complete metric and the cumulative metrics in early layers, layers with a larger \(|r_{i,d}|^{2}\) need to be considered earlier.  
Therefore, we rearrange the computation order in (14) such that the computations corresponding to a larger \(|r_{i,d}|^{2}\) are performed earlier. Layers with larger expected metrics are considered earlier in the computation of (14) to mitigate the chance of an early exclusion of the best neighbor.  
In Algorithm 1, steps 1-6 correspond to layer ordering. Specifically, \(\underline{r}_{d}\) in step 3 denotes the \(d\)th column of the \(\mathbf{R}\) that is sorted by its expected metric in descending order. When layer ordering is not applied, \(\underline{r}_{d}\) is set to the original \(\mathbf{r}_{d}\) in step 8. Steps 10-11 are for initializing the current solution with \(\mathbf{x}_{2\!F}\). Steps 12-32 represent the search process, which is incorporated with the ENR-QR-TS. Steps 27-29 correspond to checking the tabu list L; if the tabu list if full, the first element is released to make a space for the current solution. Finally, steps 30-31 checks for the stopping criteria, such as \(p\).  
Figure 1: The ENR operation for k = 1 and L = 8.  
```
1:H,y,M
2:Output:x\({}_{\text{TS}}\)
3:if layer ordering is used then
4:for\(i=1\) to \(L\)do
5:for\(d=1\) to \(N\)do
6: Find \(\underline{r}_{d}\) by sorting the elements in \(\mathbf{r}_{d}\) in descending order of \(|r_{i,d}|^{2}\).
7:endfor
8:else
9:\(\underline{r}_{d}=\mathbf{r}_{d}\)
10:endif
11:x\({}_{\text{ZF}}=\mathbf{H}^{\dagger}\mathbf{y}\)
12:Initialize \(\mathbf{x}_{\text{TS}}=\mathbf{x}_{\text{ZF}}\) and \(\mathbf{x}^{(c)}=\mathbf{x}_{\text{ZF}}\).
13:for\(m=1\) to \(M\)do
14: Find the neighbor set \(\mathbb{N}(\mathbf{x}^{(c)})\) and the set of different positions \(\mathcal{D}\).
15:\(L=\mathbb{N}(\mathbf{x}^{(c)})\)
16:for\(i=1\) to \(N\)do
17:for\(l=1\) to \(L\)do
18: Compute the \(\phi_{i}(\mathbf{x})\) in (14) for each neighbor \(\mathbf{x}\in\mathbb{N}(\mathbf{x}^{(c)})\)
19:endfor
20: Exclude the neighbors with the \(k\) largest \(\phi_{i}(\mathbf{x})\) from \(\mathbb{N}(\mathbf{x}^{(c)})\)
21: Update the number of neighbors: \(L=L-k\).
22:endfor
23: Determine the best neighbor \(\mathbf{x}^{(b)}\) with the minimum metric.
24: Update the current solution as \(\mathbf{x}^{(c)}=\mathbf{x}^{(b)},\phi(\mathbf{x}^{(c)})=\phi(\mathbf{x}^{(b)})\)
25:if\(\phi(\mathbf{x}^{(c)})<\phi(\mathbf{x}_{\text{TS}})\)then
26: Update the best solution as \(\mathbf{x}_{\text{TS}}=\mathbf{x}^{(c)},\phi(\mathbf{x}_{\text{TS}})=\phi( \mathbf{x}^{(c)})\).
27:endif
28:if Tabu list \(\mathbb{L}\) is full then
29: Release the first element in \(\mathbb{L}\).
30:endif
31: Update the tabu list \(\mathbb{L}\) with \(\mathbf{x}^{(c)}\), \(p=p+1\)
32: Check for the stopping criteria [15].
33:endfor
```  
**Algorithm 1** ENR-QR-TS with layer ordering.