# Optimized Accelerated Over-Relaxation Method for Robust Signal Detection: A Metaheuristic Approach
## 4 Analysis of Computational Complexity  
The OAOR method's computational complexity in terms of complex-valued multiplications can be derived by analyzing its two main components, i.e., the iterative detection process and the novel PSO algorithm. To begin, let us consider the OAOR iteration Equation (6), where \(\mathbf{x}^{(k)}\) is the signal estimate, \(\omega^{*}\) and \(\gamma^{*}\) are optimized parameters, and \(\mathbf{D},\mathbf{L}\), and \(\mathbf{U}\) are components of the channel matrix \(\mathbf{G}\). Here, major operations are the two matrix-vector multiplications (\(\mathbf{G}^{H}\mathbf{r}\) and \(\mathbf{G}^{H}\mathbf{G}\mathbf{x}^{(k)}\)) and several vector additions and scalar multiplications. The matrix-vector multiplications dominate the complexity, each requiring \(O(K^{2})\) operations for a system with \(K\) users. Summing up these operations and accounting for \(i\) iterations, we derive the iterative part's complexity as \(C_{\text{iter}}=O(iK^{2})\), or more precisely, \(i(2K^{2}+4K)\) complex multiplications.  
As OAOR includes the novel PSO for obtaining the optimized parameters, its fitness function is evaluated to reduce the mean square error. The PSO algorithm operates on a population of \(P\) particles over \(T\) iterations. In each detection, for the given particles, the fitness function is evaluated to update the particle's velocity and position and update the personal and global best solutions. The fitness function, which estimates the mean square error, is the most computationally expensive part. A straightforward implementation of the fitness function would involve operations similar to an OAOR iteration with the complexity of \(O(K^{2})\). However, we can optimize this here using the sampling technique and approximation, reducing it to \(O(K\log(K))\), keeping in mind that it will be a one-time cost for that particular system's configuration and channel conditions, and will not impact each iteration. To compute its complexity, we multiply the number of particles (\(P\)), the number of iterations (\(T\)), and the fitness function complexity: \(C_{\text{PSO}}=O(PTK\log(K))\). This shows that OAOR maintains an overall complexity order of \(O(K^{2})\), lower than the \(O(K^{3})\) complexity of MMSE detection for large \(K\). To illustrate, consider a system with \(K=128\) users. MMSE would require \(O(128^{3})\approx\) 2,097,152 operations, while OAOR with \(i=4\) iterations would need \(O(4*128^{2})\approx\) 65,536 operations for the iterative part, plus the PSO contribution. Even with PSO, the complexity of OAOR remains substantially lower than MMSE for this large system. This means the efficiency of OAOR is more promising as the number of users \(K\) increases. This point also has more of an advantage than the traditional AOR method and makes OAOR more advantageous in terms of the scalability of large antenna systems. To further validate our proposed method's complexity, we compare it with the complexities of AOR, IGS, and efficient successive over-relaxation (E-SOR) algorithms. We can evaluate from the performance results that our proposed method has a good balance between complexity and detection accuracy. The comparison of the complexity of these algorithms is given in Figure 4. In this figure, although AOR has lower complexity in detection performance, it does not achieve the optimal results of detection accuracy within the same iteration count as the proposed method. Similarly, the complexity of the IGS method is increased for higher iteration counts, (i.e., \(\geq\) 5) when the antenna configuration ratio is very small, thus requiring higher iterations to attain near-MMSE performance. So, overall, our proposed method presents an optimal trade-off between complexity and performance.