# 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  
Algorithm 1 outlines the procedure for anomaly detection using the proposed PLsBD and \(\alpha\)-relative Pearson divergence (\(\alpha\)-PE), incorporating both \(L_{1}\) and \(L_{2}\) loss functions for parameter learning. This algorithm is adapted from the change-point detection method described in our recent work [35], with a key difference: in anomaly detection, the training data window remains fixed, whereas in change-point detection, both the training and testing data windows slide simultaneously from left to right. The anomaly detection process involves four main steps:  
1. **Data Preparation**: The dataset is divided into training and test sets. The training set consists only of normal samples, while the test set may include anomalies. The algorithm computes distribution divergences between the training and test samples by sliding a window from left to right. 2. **Parameter Optimization**: Cross-validation is used to determine the optimal values of parameters, including kernel width (\(\sigma\)) and regularization term (\(\lambda\)). 3. **Density Ratio Estimation**: Both the least absolute deviation (\(L_{1}\)) and least-squares loss (\(L_{2}\)) approaches employ kernel computations to compute the optimal coefficients (\(\theta\)), which are then used to estimate density ratios. 4. **Anomaly Identification**: Divergence scores, either PLsBD or \(\alpha\)-PE, are calculated, and samples are flagged as potential anomalies if their scores exceed a predefined percentile threshold of the maximum score. Then, the sliding window is moved to the right, and the procedure is repeated. Notably, setting \(\alpha=0\) reduces the method to the unconstrained least-squares importance fitting (uLSIF), a state-of-the-art technique for density ratio estimation and anomaly detection [37]. ``` Input: Training samples \(\{x_{j}^{tr}\}_{j=1}^{n_{tr}}\), test samples \(\{x_{i}^{te}\}_{i=1}^{n_{tr}}\), number of folds in cross-validation, \(k\), mixing parameter \(\alpha\), number of basis functions \(n_{b}\), threshold \(\tau\in[0,1]\). Output: Anomaly candidates. Step 1: Optimal Parameter Selection via Cross-Validation

For each \(\sigma,\lambda\) value,

* For each \(\sigma\) and \(\lambda\), perform \(k\)-fold cross-validation:

* Compute the kernel matrix \(K_{\sigma}(x,x^{\prime})\). * Calculate \(\widehat{\mathbf{h}}_{tr}\), \(\widehat{\mathbf{h}}_{te}\), and \(\widehat{\mathbf{H}}\). * Apply \(n_{f}\)-fold cross validation to identify optimal \(\sigma\) and \(\lambda\). Step 2: Estimator Learning by Solving Optimization Problems

Using the optimal values of \(\sigma\) and \(\lambda\),

* For the \(L_{1}\) loss-based optimization, solve \[\hat{\boldsymbol{\theta}}=\left(\alpha\widehat{\mathbf{h}}_{tr}+(1-\alpha) \widehat{\mathbf{h}}_{te}\right)^{-1},\]
* For the \(L_{2}\) loss-based optimization problem, solve \[\hat{\boldsymbol{\theta}}=(\widehat{\mathbf{H}}+\lambda\mathbf{I}_{n})^{-1} \widehat{\mathbf{h}}_{tr},\] Step 3: Calculation of Divergence Score
* Compute the estimated density ratio \(\hat{w}(x)=\sum_{i=1}^{n_{tr}}\hat{\theta}_{i}K_{\sigma}(x,x_{i}^{tr})\). * Calculate the divergence between training and testing data:
* PLsBD divergence: \[\widehat{PL}(p_{tr}\|p_{te};m_{\alpha})\approx\frac{1}{2n_{tr}}\sum_{i=1}^{n_ {tr}}\hat{w}(x_{i}^{tr})-\frac{2-\alpha}{2(1-\alpha)}\sum_{i=1}^{n_{tr}}\hat{ w}(x_{i}^{te})+\frac{1}{2(1-\alpha)}.\]
* \(\alpha\)-relative PE divergence: \[\widehat{\alphaPE}(p_{tr}\|p_{te};p_{te,\alpha}(x))\approx\frac{1}{2n_{tr}} \sum_{i=1}^{n_{tr}}\hat{w}(x_{i}^{tr})-\frac{1}{2}.\] Step 4: Identify Anomaly Candidates
* Identify the maximum divergence score: \(\widehat{PL}_{\max}\) or \(\widehat{\alphaPE}_{\max}\).