
For each row in \(X\in \mathbb {R}^{m \times n}\)  considered as a point in \(\mathbb {R}^m\) , choose \(k\)  nearest points as neighbors [1]}

Consider all the point in \(X\)  as nodes and if any two nodes are chosen to be neighbors in 1), calculate Euclidean distance between them \(D=[d_{ij}^2]_{n\times n}\) ; where \(d_{ij} = \Vert x_i - x_j\Vert _2\)  and \(n\)  is the order of the high-dimensional space. This step converts the dataset into a graph.

For each pair of nodes in the graph, find the points \(\mathcal {G}=\big \lbrace x_i\vert i=1 \dots , k\big \rbrace \)  in the shortest path using Floyd's algorithm [2]} and assign it to \(D_{ij}\)  for that non-neighnoring pair of nodes.

Convert the matrix of distances \(D\)  into a Gram matrix \(S\)  by double centering using \(S_{ij}=-\frac{1}{2}\big [d^2_{ij}-\mu _i(d^2) -\mu _j(d^2)+\mu _{ij}(d^2)\big ]\) , where \(\mu _i\)  is the average of the \(i\) -th row, \(\mu _j\)  is the average of the \(j\) -th column, and \(\mu _{ij}\)  is the average of all of the entries in the matrix. Note, \(S\)  is symmetric semi-positive definite if \(D\)  is a Euclidean Distance Matrix [3]}.

Compute the SVD of \(S\)  using \(S=U\Sigma V^T\) .

Finally, estimate \(k\)  dimensional latent variables as \(\hat{X}=I_{k\times n}\Sigma ^{1/2}V^T\)  where \(I_{k\times n}\)  is a \(k\times n\)  matrix with 1 on its diagonal and 0 elsewhere.

