# Anomaly Detection in High-Dimensional Time Series Data with Scaled Bregman Divergence
## 2 Materials and Methods
### Algorithm and Computational Complexity Analysis
#### 2.3.1 Anomaly Detection Algorithm
* An anomaly is detected if: \[\frac{\widehat{PL}(p_{tr}\|p_{te};m_{\alpha}(x))}{PL_{\max}}>\tau\quad\text{or} \quad\frac{\widehat{\alphaPE}(p_{tr}\|p_{te};p_{te,\alpha}(x))}{\alpha PE_{ \max}}>\tau.\]

**Algorithm 1** Anomaly detection using PLsBD and \(\alpha\)PE measures with both \(L_{1}\) and \(L_{2}\) loss functions

#### 2.3.2 Complexity Analysis of Divergence Calculation

In the comparison between Equations (4) and (5), the computation of the empirical average for the PLsBD requires \(\mathcal{O}(n_{tr}+n_{te})\) operations, while the empirical estimation of the \(\alpha\)-PE divergence requires only \(\mathcal{O}(n_{tr})\) operations. Although PLsBD incurs a slightly higher cost during empirical averaging, this overhead is negligible compared to the cost of density ratio estimation, which will be analyzed below. #### 2.3.3 Complexity Analysis of Density Ratio Estimation

Our method is based on a kernel-based density ratio estimation framework, which has computational complexity comparable to the uLSIF method analyzed by [PERSON] et al. [42]. The optimization problems can be solved using either \(L_{1}\) or \(L_{2}\) loss functions, which differ in computational complexities. **Computational Complexity of \(L_{2}\) Loss**: The computational complexity of the \(L_{2}\) loss can be broken down into the following components:

* Kernel Matrix Computation: For \(n_{tr}\) training samples, \(n_{te}\) test samples, and an \(n\times n\) kernel matrix, each kernel evaluation takes \(\mathcal{O}(d)\), where \(d\) is the feature dimensionality in the data. The total complexity is \[\mathcal{O}(n\cdot(n_{tr}+n_{te})\cdot d).\]
* Matrix Inversion: Solving \((\hat{\mathbf{H}}+\lambda I_{n})^{-1}\) has a complexity of \(\mathcal{O}(n^{3})\). * Vector Multiplication: Multiplying the inverted matrix with the \(n\)-dimensional vector \(\widehat{\mathbf{h}}_{tr}\) requires \(\mathcal{O}(n^{2})\). Thus, the total computational complexity for \(L_{2}\) loss is dominated by the kernel matrix computation and matrix inversion:

\[\mathcal{O}(n\cdot(n_{tr}+n_{te})\cdot d+n^{3}).\]

**Computational Complexity of \(L_{1}\) Loss-based Method**: The \(L_{1}\) loss avoids matrix inversion, requiring only element-wise computations and vector additions. Its complexity is therefore determined solely by the kernel matrix computation:

\[\mathcal{O}(n\cdot(n_{tr}+n_{te})\cdot d).\]

In summary, the additional \(\mathcal{O}(n^{3})\) term in \(L_{2}\) loss, arising from matrix inversion, renders it significantly more computationally expensive for large \(n\), particularly in high-dimensional kernel setups. In contrast, the \(L_{1}\) loss provides a more efficient alternative while retaining comparable performance in many scenarios. Our subsequent real-world data analysis confirmed this observation: the \(L_{2}\)-loss-based method requires considerably more computation time than the \(L_{1}\)-loss-based method, while the influence of divergences on overall performance is negligible. ## 3 Results

In this section, we will implement Algorithm 1 to evaluate the performance of the proposed and existing anomaly detection algorithms on both synthetic and real-world datasets. Specifically, we compare the performance of uLSIF, RuLSIF, and PLsBD, using both the least absolute deviation and least squared loss approaches. ### Parameter Configuration

In all experiments, the number of basis functions, represented by Gaussian kernels, is fixed at 50. Our preliminary studies indicated that 50 kernel functions are sufficient to effectively fit the model while maintaining a balance between computational cost and performance. The centers of the basis functions are randomly initialized from the test dataset, and 5-fold cross-validation method is employed to determine the optimal values of \(\sigma\) and \(\lambda\). The value of \(\alpha\) is typically chosen in the range of 0.01 to 0.1.