# Robust Hessian Locally Linear Embedding Techniques for High-Dimensional Data
## 4 Robust Hessian Locally Linear Embedding
### Robust Hessian Locally Linear Embedding  
With the above preparation, we are now ready to present our main Robust Hessian locally linear embedding algorithm. We assumed that a dataset \(X^{on}=[x_{1}^{on},x_{2}^{on},\ldots,x_{N_{all}}^{on}]\in\mathbb{R}^{D\times N}\) is sampled from a d-dimensional manifold \(\mathcal{M}\) with the existence of outliers and noise-corrupted points. Our RHLLE algorithm can be formally stated as follows:  
1. Perform the fast outlier identifying algorithm described in Section 4.2 on the dataset \(X^{on}\), and obtain the ddataset \(X^{or}=[x_{1}^{or},x_{2}^{or},\ldots,x_{N}^{or}]\) whose outliers have been removed. 2. Perform the local smoothing procedure described in Section 4.3 on the dataset \(X^{or}\), and obtain the noise reduction dataset \(X^{ur}=[x_{1},x_{2},\ldots,x_{N}]\). 3. 1. Find the \(k\) nearest neighbors for each point \(x_{i}\in X^{ur}\) as the HLLE algorithm does. 2. Compute the total reliability scores \(W_{i}^{p}\) for each local patch \(\mathcal{N}(x_{i})\), and determine the reliable local patch subset \(\mathcal{RLP}\). 3. Compute the local tangent coordinates and the local Hessian operator \(H^{i}\) for each local patch \(\mathcal{N}(x_{i})\in\mathcal{RLP}\) as described in Section 2.2. 4. Compute the weighted global functional \(\bar{\mathcal{H}}_{w}\) instead of the global functional in Equation (11) which measures the average \"curviness\" of the manifold \(\mathcal{M}\): \[\bar{\mathcal{H}}_{w}=\sum_{\mathcal{N}(x_{i})\in\mathcal{RLP}}W_{i}^{p}S^{i }(H^{i})^{T}(H^{i})(S^{i})^{T}\] (22)
4. Perform an eigenanalysis of \(\bar{\mathcal{H}}_{w}\) and choose the low-dimensional embedding coordinates \(Y\) to be the eigenvectors of \(\bar{\mathcal{H}}_{w}\) with \(d\) smallest eigenvalues, excluding the constant eigenvector. Our RHLLE algorithm makes HLLE more robust from three aspects. In the first step of the algorithm, we use our proposed fast outlier identifying algorithm to remove the outliers. In the second step, we employ the local smoothing algorithm to reduce the influence of noise-corrupted data points. To further reduce the undesirable effects of outliers and noises on the embedding result, in the third step, we compute the local Hessian operators based on the selected reliable local patches and endow the reliable local patches with different weights to construct the weighted global functional. In order to compute the total reliability scores \(W_{i}^{p}\) in Step 3 (b) of our RHLLE algorithm, we first compute the total reliability scores \(s_{j}\) for each point \(x_{j}\) according to Equation (21). Then the total reliability scores \(W_{i}^{p}\) for each local patch \(\mathcal{N}(x_{i})\) can be defined as follows:\[W_{i}^{p}=\sum_{x_{j}\in\mathcal{N}(x_{i})}s_{j} \tag{23}\]  
The above total reliability scores \(W_{i}^{p}\) can be used to qualitatively classify the local patches into two classes: the reliable local patches and unreliable local patches. In the reliable local patch, clean data points are preponderant, in contrast, the unreliable local patch usually contains data points that diverge from the underlying manifold. Therefore, the total reliability score in the reliable local patch is much larger than that of the unreliable local patch. Following the ideas of robust statistics [25], we set the threshold value to be \(\theta=\frac{1}{2N}\sum_{i=1}^{N}W_{i}^{p}\); then, the reliable local patch subset can be formally defined as:  
\[\mathcal{RLP}=\{\mathcal{N}(x_{i}):W_{i}^{p}\geq\theta\} \tag{24}\]  
At the end of this subsection, we compare our RHLLE algorithm to the RLLE [15] and RLTSA [17] algorithms. All these methods develop the corresponding weighted cost function instead of the original one to reduce the undesirable effect of outliers or noises. However, there are three significant differences among them. Firstly, both RLLE and RLTSA use RPCA technique to identify the outliers, while our RHLLE develops a fast algorithm to identify the outliers.