# Robust Hessian Locally Linear Embedding Techniques for High-Dimensional Data
## 4 Robust Hessian Locally Linear Embedding
### Fast Outlier Identifying Algorithm
#### Step 2  
After we obtain the iterative solution of \(\bar{x_{i}}\), we further update the weights \(w_{j}^{i}\) based on the idea from robust statistics. Specifically, we perform weighted PCA and compute the reconstruction errors for all the \(k\) samples from the local patch. Then, we update the weights by the weight function defined as:\[w_{j}^{i}=w(\dot{e}_{j}^{i})=\frac{\rho^{\prime}(\dot{e}_{j}^{i})}{\dot{e}_{j}^{i} }=\begin{cases}1,&\dot{e}_{j}^{i}\leq\frac{1}{2}c\\ \frac{c}{2\dot{e}_{j}^{i}},&\dot{e}_{j}^{i}>\frac{1}{2}c\end{cases} \tag{19}\]  
where \(\rho^{\prime}(\cdot)\) is the first derivative of \(\rho(\cdot)\) which is called the Huber function [33] and defined as:  
\[\rho(\varepsilon)=\begin{cases}\frac{1}{2}\varepsilon^{2},&|\varepsilon|\leq c \\ c(|\varepsilon|-\frac{1}{2}c),&|\varepsilon|>c\end{cases} \tag{20}\]  
where \(c>0\) is a user-defined parameter. In this paper, the value of \(c\) is set according to the mean value of the projection errors; thus, \(c=\tilde{e}^{i}=\frac{1}{k}\sum_{k=1}^{-1}\varepsilon_{j}^{i}\).  
It is worth noting that the computational complexity of the iterative procedure in Step 1 of our proposed algorithm is about \(O(kNLD)\), where \(L\) is the assumed average iterative times. It is much lower than the computational complexity of the iterative procedure in RPCA, which is \(O(kNLDD^{2})\). In Step 2, we update the weights in one iteration. This procedure has the complexity of \(O(kNdD^{2})\) which is \(1/L\) of that of the RPCA algorithm. Therefore, comparing with the original RPCA, our proposed two-step approach can save the computation time effectively, especially for high-dimensional data (when \(D\) is large).  
After performing our robust two-step algorithm on the local patch, each point \(x_{j}^{i}\) in it has an associated weight \(w_{j}^{i}\). In order to identify the outliers, we compute the normalized weight as \((w_{j}^{i})^{*}=w_{j}^{i}/\sum_{j=1}^{k}w_{j}^{i}\). For other points that are not in the local patch containing \(x_{i}\), we set their normalized weight to 0. The normalized weights give us a measure on how likely each sample comes from the underlying data manifold that we can infer from the corresponding local patch. Then we can obtain the total reliability score of each point by summing up the normalized weights computed from all the local patches. The total reliability score of each point \(x_{j}(j=1,2,\ldots,N)\) can be defined as:  
\[s_{j}=\sum_{i=1}^{N}(w_{j}^{i})^{*} \tag{21}\]  
The total reliability score is very small for outliers, while the total reliability score of clean points is relatively large. Therefore, we can identify the outliers based on the reliability scores, _i.e._, a point \(x_{j}\) is identified as an outlier if and only if \(s_{j}\leq\alpha\) for some threshold \(\alpha>0\). Furthermore, we can plot the cumulative distributions of reliability scores for the dataset to make it easier to choose the appropriate value of \(\alpha\). Figure 1(d),e show the cumulative distributions of reliability scores for the \"Swiss roll with a hole\" dataset, where the y-axis shows the frequency counts, the x-axis indicates the reliability scores computed by the RPCA algorithm and our fast approximate algorithm respectively. The vertical dashed lines indicate the \(\alpha\) values used in our experiments (usually near a point at which the slope of the cumulative distribution curve has a large change). Figure 1(b),c show the outlier removal results by the RPCA algorithm and our fast approximate algorithm respectively. As we can see from Figure 1(b),c, both our fast approximate algorithm and the RPCA algorithm can be applied to identify and remove the outliers effectively.