## 2 Background and Related Work
### Spectral Dimensionality Reduction Methods  
Spectral dimensionality reduction (SDR) refers to a family of methods that map high-dimensional data to a low-dimensional representation by learning the low-dimensional structure in the original data. SDR methods rely on the assumption that there exists a function \(f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}\), \(d\leq D\), that maps low-dimensional coordinates, \(y_{i}\in\mathbb{R}^{d}\), of each data sample to the observed \(x_{i}\in\mathbb{R}^{D}\). The goal then becomes to learn the inverse mapping, \(f^{-1}\), that can be used to map high-dimensional \(x_{i}\) to low-dimensional \(y_{i}\). While different methods exist within this family, they all share a common computing pattern. For a given set of points, \(\mathbf{X}\), in a high-dimensional space \(\mathbb{R}^{D}\), SDR methods compute either top or bottom eigenvectors of a feature matrix, \(\mathbf{F}\) derived from the \(n\times D\) data matrix, \(\mathbf{X}\), where \(n\) is the number of data instances. Here, the feature matrix, \(\mathbf{F}\), captures the structure of the data through some selected property (e.g., pairwise distances). Two broad categories of SDR methods exist, based on the assumption they make about \(f\) (i.e., linear vs. nonlinear). Linear methods assume that the data lie on a low-dimensional subspace \(\mathbb{V}^{d}\) of \(\mathbb{R}^{D}\), and construct a set of basis vectors representing the mapping. When working with the linearity assumption, the most commonly used methods are PCA and multidimensional scaling (MDS) [11]. PCA learns the subspace that best preserves covariance, i.e., \(F\) is the \(D\times D\) sample covariance matrix of the input data. The basis vectors learned by PCA, known as principal components, are the directions along which the data has highest variance. In the case of MDS, the feature matrix is the \(n\times n\) dissimilarity matrix that encodes some pairwise relationships between data points in \(\mathbf{X}\). When these relationships are Euclidean distances, the result is equivalent to that of PCA, and this is known as classical MDS. Spectral decomposition of \(\mathbf{F}\) in both methods yields eigenvectors \(\mathbf{Q}\). Taking the top \(d\) eigenvectors, the data can be mapped to low-dimensions as \(\mathbf{Y}\) by the transformation \(\mathbf{Y}=\mathbf{X}\mathbf{Q}_{d}\). However, in cases where the data is assumed to be generated by some nonlinear process, the linearity assumption is too restrictive. In such cases, both PCA and MDS are not robust enough to learn the inverse mapping \(f^{-1}\). Although variants of PCA have been proposed to address such situations (e.g., kernel PCA [12]), their performance is sensitive to the choice of the kernel and the associated parameters. Instead, the most common approach is to use a manifold learning-based nonlinear SDR (or NLSDR) technique, such as Isomap [2]. NLSDR techniques can be divided into two categories: _global_ and _local_. Global methods, e.g., Isomap, minimum volume embedding [13], preserve a global property of the data. On the other hand, local methods, e.g., local linear embedding (LLE) [14; 15], diffusion maps [16], Laplacian eigenmaps [17], preserve a local property for each data instance. All of these methods, however, involve a series of similar data transformations. First, a neighborhood graph is constructed, in which each node is linked with its \(k\) nearest neighbors. Next, this neighborhood graph is used to create a feature matrix which characterizes the property that the underlying algorithm is trying to preserve. For Isomap, the feature matrix is obtained as the shortest path graph in which every pair of data instances is connected to each other by the shortest path between them. The low-dimensional representation of the input data is obtained by factorization of the feature matrix. Typically, first \(d\) eigenvectors/values form the output \(Y\). The steps of the Isomap algorithm are outlined in Algorithm 1.