Eigenvalue/eigenvector techniques are commonly used to uncover low-dimensional linear subspaces embedded in higher-dimensional spaces. Given a collection of points in a P-dimensional space, the eigenvalues of the covariance matrix reveal the underlying dimensionality of the space. Specifically, the points live on a Q-dimensional linear subspace, where Q<=P is the number of non-zero eigenvalues of the covariance matrix. For example, the blue points shown on the right live on a 2-D linear subspace of the full 3-D space. The eigenvalues of the covariance matrix are 1.0, 0.34, 0.0, revealing the underlying two-dimensional linear subspace.

However, if the points live on a non-linear manifold then this approach is ineffective in revealing the underlying dimensionality. For example, the red points live on a 2-D non-linear manifold (a parabolic cylinder). The eigenvalues of the covariance matrix are 1.0,0.9,0.6, which do not reveal the two-dimensional nature of this manifold.

Outlined below is a simple approach (see "Mapping a Manifold of Perceptual Observations", J.B. Tenenbaum, NIPS 98.) for determining the intrinsic dimensionality of a certain class of non-linear manifolds.

1. Given N points in a P-dimensional space, construct a non-parametric manifold (a graph)
   • choose a random subset of M points (vertices)
   • for each point P_i, i = 1,...,N compute the Euclidean distance to each of the M points
   • create an edge between the two points Q and R that have the shortest distances to P_i
2. Compute the manifold distance between all pairs of M points
   • using Floyd's algorithm, compute D, the M x M distance matrix
3. Perform metric multi-dimensional scaling (MDS) on D
   • i.e., determine if there is a projection from the original P-dimensional subspace to a lower dimensional subspace that preserves the manifold distances (not Euclidean distances). The solution is analytic and involves an eigenvalue/eigenvector analysis of the distance matrix D.