## 2 Linear Projections for Manifold Learning
### LPP and NPE  
The LPP and the NPE are linear manifold learning methods that are derived from the LE and the LLE, respectively. Given a set for training data is \(X=[x_{1},\ x_{2},\ \ldots,x_{m}]\) in \(R^{n}\), they aim to find a transformation matrix, \(A=[a_{0},\ a_{1},\ \ldots a_{l-1},]\) that maps \(X\) to \(Y=[y_{1},\ y_{2},\ \ldots,y_{m}]\) in \(R^{l}\) to obtain lower dimensional space. The methods use the following equation for the linear projection:  
\[x_{i}\ \rightarrow\ y_{i}=A^{T}x_{i} \tag{1}\]  
In the LPP [13], the first step is to construct the adjacency graph. The nodes \(i\) and \(j\) are connected if \(i\) is in k-nearest neighbors of \(j\). The following Euclidean distance formulation is used to determine the distances between the nodes:  
\[d\big{(}x_{i},\ x_{j}\big{)}=\sqrt{\big{(}x_{i1}-x_{j1}\big{)}^{2}+\big{(}x_{i 2}-x_{j2}\big{)}^{2}+\ldots+\big{(}x_{in}-x_{jn}\big{)}^{2}} \tag{2}\]  
The next step of the LPP is to construct the weights. Weights on the connected nodes are calculated by a heat kernel function given by Equation (3). If the nodes \(i\) and \(j\) are not connected, then, it is represented by \(0\) in the \(W\). \(W\) is a symmetric, \(m\times m\) weight matrix as follows:  
\[W_{ij}=e^{-\frac{||x_{i}-x_{j}|^{2}}{t}} \tag{3}\]  
where \(t=2s^{2}\). The heat kernel parameter, \(s\), is used in the experiments later.  
The algorithm continues with the minimization of Equation (4) assuming \(y^{T}=a^{T}X\), where \(\alpha\) is the transformation vector as follows:  
\[\sum_{i,j}\big{(}y_{i}-y_{j}\big{)}^{2}W_{ij} \tag{4}\]  
Finally, the minimization problem leads to a generalized eigenvalue problem as follows:  
\[XLX^{T}a_{i}=\lambda_{i}XDX^{T}a_{i} \tag{5}\]  
where \(L\) and \(D\) represent the Laplacian and diagonal matrices, respectively, and are defined as \(L=D-W\) and \(D_{ii}=\sum\limits_{j}W_{ji}\), respectively. The transformation matrix, \(A\), is constructed as \(A=[a_{0},\ a_{1},\ \ldots a_{l-1},]\), where \(a_{0},a_{1},\ \ldots,\ a_{l-1}\) corresponds to \(l\) smallest eigenvalue such that \(\lambda_{0}<\lambda_{1}<\ldots<\lambda_{l-1}\). \(A\) is substituted into Equation (1) to obtain the low-dimensional space that represents high-dimensional data.  
NPE provides linearization to the LLE algorithm as stated formerly [16]. The first step of the algorithm is to construct the adjacency graph, as in the LPP. This provides neighborhood information. Unlike the LPP algorithm, the weight matrix, \(W\), is obtained by using the convex optimization instead of the heat kernel function. Assuming \(y^{T}=a^{T}X\), the minimization of Equation (6) is solved to obtain \(W\) as follows:  
\[\sum_{i}\big{(}y_{i}-\sum_{j}W_{ij}y_{j}\big{)}^{2} \tag{6}\]Finally, the minimization problem leads to generalized eigenvalue problem as follows:  
\[XMX^{T}a_{i}=\lambda_{i}XX^{T}a_{i} \tag{7}\]  
where \(M\) equals \((I-W)^{T}(I-W)\) and \(I\) is identity matrix. As in the LPP, the transformation matrix, \(A\), is constructed as \(A=[a_{0},\ a_{1},\ \ldots a_{l-1},]\), where \(a_{0},a_{1},\ \ldots,\ a_{l-1}\) corresponds to the \(l\) smallest eigenvalues such that \(\lambda_{0}<\lambda_{1}<\ldots<\lambda_{l-1}\). Linear projection is implemented by substituting \(A\) into Equation (1) to get low-dimensional representation.