# GNSS Spoofing Detection Based on Wavelets and Machine Learning
## 4 Results and Discussion
### Computational Complexity
Extraction of statistical characteristics for the first level of approximation coefficients: \(O(n^{2})\). 5. Extraction of spectral features and FFT: \(O(n^{2}\cdot logn)\). 6. Saving features to.csv file: \(O(1)\). 7. Generating and saving DWT image (A1 img) in.tiff format: \(O(n^{2})\). 8. Feature extraction from the.tiff image: * Histogram per RGB channel: \(O(n^{2}\cdot C)\), where \(C\) is the number of channels of the image (three channels for RGB). * Gradient magnitude: \(O(n^{2}\cdot C)\). * Textural features: \(O(n^{2}\cdot C+G\cdot C)\), where \(G\) is the number of GLCM metrics (e.g., contrast, correlation, energy, and homogeneity). The total complexity per iteration is \(O(n^{2}\cdot logn+n^{2}\cdot C)\). The dominant part of computational complexity is the application of the 2D DWT transform, followed by the application of the Fast Fourier Transform and the extraction of features from images. The computational complexity for the entire processing of.bin file is \(O(R\cdot S\cdot logS)\), where \(R\) is the total number of iterations. If \(P\) and \(D\) increase, then the complexity goes over \(O(n^{2})\) which is very memory-intensive. The computational complexity increases with the use of a larger number of levels, i.e., multiple decomposition levels and for this reason, only one DWT level was used in this research, which enabled faster and simpler batch processing of.bin file. Table 5 shows the computational complexity for all machine learning and discrete waveform classification models used, where \(N\) is the total number of samples/images in the dataset, \(D\) is the number of features detected per image (it does not use the entire pixel space, but features are taken at certain grid positions; it takes 70% of the most prominent \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Code Description by Steps**} & \multirow{2}{*}{\begin{tabular}{c} **Image Processing** \\ **Algorithm** \\ \end{tabular} } & \multirow{2}{*}{\begin{tabular}{c} **Image Features**\({}^{*}\) \\ **Processing** \\ **Algorithm** \\ \end{tabular} } & \multirow{2}{*}{\
\begin{tabular}{c} **Spectral and** \\ **Statistical** \\ **Features** \\ **Processing** \\ **Algorithm** \\ \end{tabular} } & \multirow{2}{*}{
\begin{tabular}{c} **Computational** \\ **Complexity** \\ **Algorithm** \\ \end{tabular} } \\  & & & & & \\ \hline Data loading & ✓ & ✓ & ✓ & \(O(N)\) \\ Generating bag of features & ✓ & X & X & \(O(N\cdot D\cdot K\cdot I)\) \\ Images encoding & ✓ & X & X & \(O(N\cdot D\cdot K)\) \\ Assigning classes to data & X & ✓ & ✓ & \(O(N)\) \\ Table to array conversion & X & ✓ & ✓ & \(O(N\cdot d)\) \\ k-Fold cross-validation (loop, \(R\) times) & ✓ & ✓ & ✓ & \(O(R)\) \\ k-Fold training and testing in each iteration & ✓ & ✓ & ✓ & \(O(k)\) \\ Model training with Gaussian kernel & ✓ & ✓ & ✓ & \(O(M^{2}\cdot d)\) \\ Data prediction & ✓ & ✓ & ✓ & \(O(T\cdot S)\) \\ Performance metrics (F1-score, precision, recall, confusion matrix) calculation & ✓ & ✓ & ✓ & \(O(1)-O(N)\) \\ Generating ROC and PR curves & ✓ & ✓ & \(O(1)-O(N)\) \\ Graphical representation and saving the generated data & ✓ & ✓ & ✓ & \(O(N)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: SVM classification algorithms [57; 58; 59] described in steps with the computational complexity based on different type of data processing. features), \(K\) is the number of clusters in the bag-of-features model (the number of visual words), \(I\) represents the number of clustering iterations, \(R\) is the number of repetitions of k-fold cross-validation, \(k\) is the number of folds in K-fold cross-validation, \(M\) is the number of training samples per iteration, \(d\) is the dimension of the BoF vector (the number of features after encoding), \(T\) is the number of test samples, \(S\) is the number of support vectors, and \(n_{trees}\) is the number of trees in the RF model. The computational complexity of the SVM model that uses images as the input classification data consists of two parts.