Dimension Reduction Taxonomy - 6. Other Classical Methods: LDA, MDS, and Isomap

6. Other Classical Methods: LDA, MDS, and Isomap

Linear Discriminant Analysis (LDA) is a supervised method that focuses on class separability. Multidimensional Scaling (MDS) preserves pairwise distances. Isomap is an early, influential non-linear method that uses geodesic distances.

6.1 Linear Discriminant Analysis (LDA)

LDA maximizes the ratio of between-class variance to within-class variance:

The solution is the generalized eigenvalue problem:

LDA reduces dimension to at most (number of classes − 1).

LDA is a powerful supervised linear reduction technique. It finds a projection that best separates the classes by considering both the scatter between classes and the scatter within classes. In practice, LDA is used in face recognition (Fisherfaces) and document classification. The within-class scatter matrix S_W is the covariance of the class-mean centered data, while S_B is the covariance of the class means. The projection vectors are the eigenvectors corresponding to the largest eigenvalues of S_W^{-1} S_B. LDA is optimal when the classes are Gaussian with equal covariance, but it can still be effective in many real-world scenarios. One limitation is that it requires labeled data and can only produce at most c-1 dimensions, where c is the number of classes.

6.2 Multidimensional Scaling (MDS)

Classical MDS takes a pairwise distance matrix and finds an embedding that preserves distances. It computes the Gram matrix:

and performs eigenvalue decomposition. If distances are Euclidean, it is equivalent to PCA.

MDS is widely used in psychometrics and marketing to create perceptual maps. For example, it can take the pairwise similarity ratings of different brands and plot them in 2D, revealing competitive positioning. The embedding coordinates are derived from the eigenvectors of B, scaled by the square root of the eigenvalues. MDS can handle any distance metric, making it flexible, but it is computationally expensive for large datasets (O(n³)). Non-metric MDS extends the idea to ordinal or categorical dissimilarities, preserving the rank order rather than the actual distances.

6.3 Isomap (Isometric Mapping)

Isomap extends MDS by replacing Euclidean distances with geodesic distances along the manifold. The algorithm: 1) Construct a neighborhood graph. 2) Compute shortest paths. 3) Apply classical MDS to the geodesic distance matrix. It is effective for continuous manifolds but is computationally expensive (O(n³)).

Isomap was one of the first methods to demonstrate the power of manifold learning. It is particularly effective for datasets like the "Swiss roll" where Euclidean distances would cut across the manifold, but geodesic distances follow the curvature. The neighborhood graph is typically constructed using k-nearest neighbors or an ε-ball. The shortest paths are computed using Dijkstra's algorithm. The resulting geodesic distance matrix is then embedded via MDS. Isomap is sensitive to the choice of neighborhood size; too small leads to disconnected components, too large approximates Euclidean distances. Despite its computational cost, it remains a valuable tool for understanding the intrinsic geometry of data.

Applications

• Face recognition (LDA).
• Perceptual and preference mapping (MDS).
• Visualization of high-dimensional manifolds (Isomap).

Strengths and limitations