Nonlinear Spectral Dimensionality Reduction

The central limitation of linear approaches to dimensionality reduction is that they assume the data lies on or near a linear subspace. In practice this may not always be the case spaces may be locally linear, but unlike the assumption made by linear techniques, globally they may be highly nonlinear. As such, using linear techniques in such circumstances could lead to distorted results with curved areas of the data being projected on top of each other. 

Nonlinear spectral dimensionality reduction techniques seek to alleviate this problem by modelling the data not using a subspace, but a submanifold. The data is 

This section reviews some of the most popular methods for nonlinear spectral dimensionality reduction. This list of methods is by no means exhaustive, rather, the methods included in this section are chosen for their didactic value and also their popularity. Each method corresponds to an important and different paradigm to spectral dimensionality reduction as such, they are each landmarks within the landscape of spectral dimensionality reduction and provide a brief but sufficient survey of the main trends within this area. 

---

Linear approaches to spectral dimensionality reduction make the assumption that the data lies on or near a low-dimensional subspace. In such cases, linear spectral dimensionality reduction methods seek to learn the basis vectors of this low-dimensional subspace so that the input data can be projected onto the linear subspace. The two main methods for linear spectral dimensionality reduction. Principal Components Analysis and Multidimensional Scaling, are both described in this section. Although more powerful nonlinear approaches have been presented in recent years, these linear techniques are still widely used and are worthy of attention since they provide the basis for some of the subsequent nonlinear spectral dimensionality reduction algorithms. 

Fig. 23 Points sampled from a simple horseshoe shaped manifold (a). The two distances in (b) show the difference between distances as measured across the manifold and the Euclidean distance. The two end points are connected by the dotted line according to the Euclidean distance. However, their manifold distance would be the sum of inter-point distances on the path between the two points. For nonlinear spectral dimensionality reduction techniques, the manifold distances should be used so that the two end points are mapped as far away in the low-dimensional space...

Isomap [2], one of the first true nonlinear spectral dimensionality reduction methods, extends metric MDS to handle nonlinear manifolds. Whereas metric MDS measures inter-point EucUdean distances to obtain a feature matrix. Isomap measures the interpoint manifold distances by approximating geodesics. The use of manifold distances can often lead to a more accurate and robust measure of distances between points so that points that are far away according to manifold distances, as measured in the high-dimensional space, are mapped as far away in the low-dimensional space (Fig. 2.3). An example low-dimensional embedding of the S-Curve dataset (Fig. 2.1) found using Isomap is given in Fig. 2.4. 

Estimating the intrinsic dimensionality of a dataset is an important pre-processing step for spectral dimensionality reduction as embedding the dataset into its non-intrinsic dimensionality can lead to suboptimal performance of any subsequent algorithms [2]. As such, the area of intrinsic dimensionality estimation has attracted much attention over the years, especially since the advent of nonlinear spectral dimensionality reduction techniques. 

This section begins by providing a general mathematical setting within which both spectral dimensionality reduction, and the associated open problems, can be described. Then key algorithms, both linear and nonlinear, are briefly described so as to provide an important point of reference and discussion for the later discussion of open problems. 

As such, care should be taken when seeking to embed a dataset into higher dimensions. The performance of spectral dimensionality reduction methods, and in fact nonlinear dimensionality reduction methods in general, is called into question in such cases. 

---