# Robust Hessian Locally Linear Embedding Techniques for High-Dimensional Data
## 2 Reformulating HLLE through Truncation Function from Differential Manifold  
### Brief Review of Hessian LLE  
Hessian LLE may be viewed as a modification of locally-linear embedding and its theoretical framework as a modification of the Laplacian eigenmap framework by replacing the Laplacian operator with the Hessian. HLLE is guaranteed to asymptotically recover the true manifold if the manifold is locally isometric to an open connected subset of \(\mathbb{R}^{d}\)[5]. Consider a dataset \(X\), which consists of \(N\) data points \(x_{1},x_{2},\cdots,x_{N}\) in high-dimensional space \(\mathbb{R}^{D}\), and hypothesize that they lie on a smooth manifold \(\mathcal{M}\subset\mathbb{R}^{D}\) of intrinsic dimensionality \(d<D\). Let \(X=[x_{1},x_{2},\ldots,x_{N}]\in\mathbb{R}^{D\times N}\) and \(Y=[y_{1},y_{2},\ldots,y_{N}]\in\mathbb{R}^{d\times N}\) denote the matrix of all sampled points and their embedding coordinates, respectively. The objective of a manifold-based dimensionality reduction algorithm is to recover the corresponding low-dimensional coordinates \(y_{i}\in\mathcal{Y}\) of each \(x_{i}\in\mathcal{M}\). In other words, we assume \(\mathcal{M}\) is the image of some coordinate space \(\mathcal{Y}\subset\mathbb{R}^{d}\) under some smooth mapping \(\psi:\mathcal{Y}\rightarrow\mathbb{R}^{D}\). Because the mapping \(\psi\) is a locally-isometric embedding, the inverse mapping \(\phi=\psi^{-1}:\mathcal{M}\rightarrow\mathbb{R}^{d}\) provides a locally-isometric coordinate system on \(\mathcal{M}\). Let \(x\) be a fixed point in the interior of \(\mathcal{M}\), and \(T_{x}(\mathcal{M})\) be the tangent space defined at \(x\). To define the Hessian, HLLE uses the orthogonal coordinates on the tangent space to compute the Hessian of a function \(f:\mathcal{M}\rightarrow\mathbb{R}\) that is \(C^{2}\) near \(x\). Suppose that the tangent coordinate of \(x\in\mathcal{N}(x)\) is given by \(u\), where \(\mathcal{N}(x)\) is the local patch built by the point \(x\) and its \(k\) nearest neighborhoods, \(\mathcal{N}(x)=\{x,x_{1},\cdots,x_{k}\}\). Then the rule \(g(u)=f(x)=f\circ\psi(u)\) defines a function \(g:U\rightarrow\mathbb{R}\), where \(U\) is the neighborhood of \(u\in\mathbb{R}^{d}\) formed by the tangent coordinates of \(N(x)\). The Hessian of \(f\) at \(x\) in tangent coordinates can be defined as the ordinary Hessian of \(g\):  
\[(H_{f}^{tan})_{i,j}(x)=\frac{\partial}{\partial u_{i}}\frac{\partial}{\partial u _{j}}g(u)|_{u=\phi(x)} \tag{1}\]  
Although different local coordinate systems give different tangent Hessians, all of these Hessians share the same Frobenius norm \(\|H_{f}^{tan}(x)\|_{F}^{2}\), so that the following quadratic form can be well defined:  
\[\mathcal{H}(f)=\int_{\mathcal{M}}\|H_{f}^{tan}(x)\|_{F}^{2}dx \tag{2}\]  
where \(dx\) stands for the canonical measure corresponding to the volume form on \(\mathcal{M}\). The functional \(\mathcal{H}(f)\) measures the average curviness of \(f\) over the manifold \(\mathcal{M}\). The key result of [PERSON] and [PERSON] [5] is that, if \(\mathcal{M}\) truly is locally-isometric to an open connected subset of \(\mathbb{R}^{d}\), then \(\mathcal{H}(f)\) has a \((d+1)\)-dimensional null space, consisting of the constant functions and a \(d\)-dimensional space of functions spanned by the original isometric coordinates. The HLLE algorithm adapts the basic structure of LLE to estimate the nullspace of the functional \(\mathcal{H}(f)\), and has five steps:  
1. Find nearest neighbors: For each data point \(x_{i}\), find the indices corresponding to the \(k\)-nearest neighbors in Euclidean distance. Let \(\mathcal{N}(x_{i})\) denote the collection of those neighbors. 2. Obtain tangent coordinates: Perform a singular value decomposition on the points in \(\mathcal{N}(x_{i})\), getting their tangent coordinates. 3. Develop Hessian estimator: Develop the infrastructure for least-squares estimation of the local Hessian operator \(H^{i}\). 4.