# GNSS Spoofing Detection Based on Wavelets and Machine Learning
## 4 Results and Discussion
### Computational Complexity
The first part refers to the generation of the bag of features, while the second part refers to the k-fold cross-validation. The most critical term can be highlighted as \(M^{2}\), which grows quadratically for the Gaussian kernel (it can go up to \(M^{3}\)). The computational complexity of this model can be reduced by reducing the image resolution, converting the image to gray scale, using a linear kernel instead of a Gaussian kernel, extracting features, reducing the number of validation iterations, and reducing the number of folds (for this reason, in this study, the number of iterations was equal to three and the number of folds was five). If we compare the algorithm that uses and processes images as the input data, i.e., that generates a BoF, and algorithms that use image features and statistical and spectral features, it can be concluded that the algorithm that uses the BoF approach is more complex because it includes the extraction of key features, clustering into visual words, and encoding each image into a word histogram. On the other hand, algorithms that use precomputed features are much easier to process (lower complexity, faster processing, and lower memory requirements) because there is no need for feature extraction, image decoding, or clustering. In the KNN model, no explicit data training is performed, but the model stores all the training data, so the computational complexity for training is negligible and amounts to \(O(1)\)[60]. In the KNN model that has images as input data, the BoF approach is also the most complex step. KNN classification is simpler to implement but has quadratic complexity in terms of the number of data for prediction, which can be complex for large datasets. BoF feature extraction and RF model training are the most dominant members of the computational complexity of an RF model that uses images as input data [46]. In the case of precomputed features, the dominant members are parsing the.csv files and training the model due to the number of trees. This algorithm is faster than RF with images because it does not use BoF. It is suitable for large datasets, and the complexity depends on the number of trees, the number of features, and the size of the dataset. The highest computational complexity is that of KNN with images as input because it has a quadratic complexity in the number of samples \(N^{2}\), and in combination with BoF image processing, it represents the most complex approach. On the other hand, the lowest complexity is that of the SVM which uses pre-extracted features, because it does not have a quadratic complexity of \(N^{2}\) nor any BoF processing, and if \(M\) is not too large, this is the simplest approach in terms of computational complexity. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Classification Data** & **SVM** & **KNN** & **RF-100/200** \\ \hline Images & \(O(N\cdot D\cdot K\cdot I+R\cdot k\cdot(M^{2}\cdot d+T\cdot S\cdot d))\) & \(O(N\cdot D\cdot K\cdot I+R\cdot N^{2}\cdot d)\) & \(O(N\cdot D\cdot K\cdot I+R\cdot k\cdot n_{trees}\cdot N\cdot logN\cdot d)\) \\ \hline Image-extracted features & \(O(N\cdot d+R\cdot k\cdot M^{2}\cdot d)\) & \(O(N\cdot d+R\cdot N^{2}\cdot d)\) & \(O(N\cdot d+R\cdot k\cdot n_{trees}\cdot N\cdot logN\cdot d)\) \\ \hline Statistical and spectral features & \(O(N\cdot d+R\cdot k\cdot M^{2}\cdot d)\) & \(O(N\cdot d+R\cdot N^{2}\cdot d)\) & \(O(N\cdot d+R\cdot N^{2}\cdot d)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Computational complexity for ML methods based on different classification data.