# Robust Hessian Locally Linear Embedding Techniques for High-Dimensional Data
## 2 Reformulating HLLE through Truncation Function from Differential Manifold
### Reformulating Hessian LLE  
The original implementation of HLLE lacks a straightforward interpretation about the construction of the approximated Hessian functional \(\tilde{\mathcal{H}}\) in Step 4. The original implementation also lacks an unambiguous explanation about the estimation of the local Hessian operator \(H^{i}\) in Step 3. Furthermore, it is time consuming to use SVD to compute the tangent coordinates for the high-dimensional data. In this subsection, we present an alternative way to formulate HLLE. The truncation function from differential manifold [24] is employed for relating the locality and the global structure of the manifold. In the given framework, a straightforward interpretation about the construction of the approximated Hessian functional explicitly appears. For completeness, we also give an unambiguous explanation about the estimation of the local Hessian operator and the tangent coordinates in this subsection. It is worth noting that [PERSON] _et al._[26] also propose a similar way to estimate the Hessian energy using the local tangent coordinates in the context of semi-supervised regression. The proposed work is focused on the context of dimensionality reduction while the work in [26] is focused on the context of semi-supervised regression. The essence of the two works in the estimation of the local Hessian operator and the tangent coordinates is the same. However, our expression and formulation is easier to follow. Recently, based on the local tangent coordinates, [PERSON] _et al._[27; 28] proposed a parallel vector field approach to approximate a second order operator, the connection Laplacian, which can also be used to approximate the Hessian operator. In order to estimate the local tangent coordinates, we first perform PCA on the points in \(\mathcal{N}(x_{i})\) and get \(d\) leading PCA eigenvectors \(V^{i}=\{v_{1}^{i},v_{2}^{i},\ldots,v_{d}^{i}\}\), which correspond to an orthogonal basis of \(T_{x_{i}}(\mathcal{M})\) (seen as a \(d\)-dimensional affine subspace of \(\mathbb{R}^{D}\) that is tangent to \(\mathcal{M}\) at \(x_{i}\)). The trick presented by [PERSON] and [PERSON] for EigenFaces [29] is employed for high-dimensional data. Then the local tangent coordinates \(\{u_{j}^{i}\}_{j=1}^{k}\) of a point \(x_{i}\in\mathcal{N}(x_{i})\) can be computed by projecting the local neighborhoods to this tangent subspace:  
\[u_{j}^{i}=\langle V^{i},x_{j}-x_{i}\rangle=(V^{i})^{T}(x_{j}-x_{i}) \tag{3}\]  
It is worth noting that we fix the origin of the tangent space at \(x_{i}\) to be the data sample itself, while the original algorithm uses the mean of the neighborhood \(\mathcal{N}(x_{i})\) of \(x_{i}\) to be the origin of the tangent space. When the dataset is non-uniformly distributed or sparse, it is lack of enough data samples to form different neighborhoods in some regions. Therefore, the local tangent spaces computed for the data samples in these regions will become the same. As a consequence, the tangent coordinates of the data samples will be biased. According to [30], the above correction of the origin of the tangent space can overcome the drawbacks of tangent space approximation in dealing with sparse or non-uniformly distributed-data-manifolds. In order to estimate the local Hessian operator, we first perform a second-order Taylor expansion at a fixed \(x_{i}\) on the smooth functions: \(\{f(x_{j})\}_{j=1}^{k},f:\mathcal{M}\rightarrow\mathbb{R}\) that is \(C^{2}\) near \(x_{i}\). \[f(x_{j})=f(x_{i})+(\
abla f)^{T}(x_{j}-x_{i})+\frac{1}{2}(x_{j}-x_{i})^{T}H_{ f}^{i}(x_{j}-x_{i})+O(\|x_{j}-x_{i}\|^{3}) \tag{4}\]  
Recall that we have defined a function \(g:U\rightarrow\mathbb{R}\) which uses the local tangent coordinates and satisfies the rule \(g(u)=f(x)=f\circ\psi(u)\) in Section 2.1.