# Support Vector Machine-Based Transmit Antenna Allocation for Multiuser Communication Systems
## 4 Numerical Evaluation
### Complexity Analysis and Runtime Evaluation  
Selection complexities are compared in Table 2. The complexity of the optimization-based algorithm is discussed in Section 2.2, and the complexity of random antenna selection is \(\mathcal{O}(1)\) because the only task is to generate a random integer. For the machine learning-based algorithms, selection complexity is defined as the online prediction complexity, excluding the training complexity since training can be completed offline with more powerful computing resources before the communication phase. In the \(k\)-NN algorithm, the complexity of \(\mathcal{O}\left(DN_{t}U\right)\) and \(\mathcal{O}\left(Dk\right)\) comes from the computing distances to all training samples and finding the \(k\) nearest neighbors, respectively [58]. In multiclass SVM algorithms, for the OVO strategy, because \(M=\frac{L(L-1)}{2}\) binary SVM learners are employed for the multiclass prediction, complexity is given by \(\mathcal{O}\left(L^{\prime 2}N_{t}U\right)\); while for the OVA strategy, \(L\) binary SVM learners are required, and thus complexity is \(\mathcal{O}\left(L^{\prime}N_{t}U\right)\)[57]. Note that the complexity of the learning-based methods mainly depends on the number of classes, and the number of classes can be reduced from \(L\) to \(L^{\prime}\), as discussed in Section 3.1. From Table 2, it can be seen that the selection complexity of the machine learning-based algorithms (\(k\)-NN and SVM) is polynomial on \(N_{t}\) and \(U\), which is lower than that of the optimization-based algorithm using exhaustive search among all potential antenna allocation schemes.  
Now, the runtime complexity (in seconds) of the online antenna selection is evaluated under the various simulation environments. Figure 11 shows runtime complexity over \(L^{\prime}\) when \(N_{t}=5\), \(U=3\), and \(L^{\prime}\in\{1,2,4,8,16,32,60\}\). It can be seen that the complexity of \(k\)-NN is much higher than that of OPT when \(L^{\prime}\geq 4\). Since the complexity of \(k\)-NN is proportional to \(D\), as shown in Table 2, the complexity of \(k\)-NN can be reduced at the cost of a degraded sum rate. On the other hand, the complexity of SVM is much lower than that of OPT; therefore, SVM is favorable for our antenna selection system.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Algorithm** & **OPT** & **RAND** & \(k\)**-NN** & **SVM** \\ \hline Sum-rate performance & Best & Worst & Close to SVM & Second-best \\ Allocation complexity & \(\mathcal{O}\left(\frac{U^{\prime}N_{t}U}{N_{t}-U\right)}\) & \(\mathcal{O}(1)\) & \(\mathcal{O}\left(DN_{t}U+Dk\right)\) & \(\mathcal{O}\left(L^{\prime 2}N_{t}U\right)\) for OVO and \(\mathcal{O}\left(L^{\prime}N_{t}U\right)\) for OVA \\ \hline \hline \end{tabular}
\end{table}
Table 2: Performance and allocation complexity of the algorithms. OVO: one-vs-one strategy; OVA: one-vs-all strategy  
Figure 10: Sum rate over \(N_{t}\) when \(L^{\prime}=60\) and \(U=2\).  
In Figure 12, we plot the runtime complexity over \(N_{t}\) from 5 to 12 when \(U=3\). We observe that the complexity of SVM is further reduced and remarkably lower than that of OPT when \(L^{\prime}=32\). More specifically, the complexity of SVM tends to increase slowly on a linear scale with \(N_{t}\), whereas that of OPT dramatically increases as \(N_{t}\) increases (refer to Table 2). However, the complexity of \(k\)-NN is still much greater than that of OPT.