Eigenvalue Problems and the LTSA Algorithm for Nonlinear Dimensionality
Reduction

Qiang Ye
Department of Mathematics
University of Kentucky
Lexington, Kentucky  40506-0027


Given a set of high-dimensional data points, the goal of
dimensionality reduction is to find a low-dimensional
parametrization for them. Usually it is easy to carry out
this parametrization process within a small region through
linearization to produce a collection of local coordinate systems.
Alignment is the process to stitch those local systems
together to produce a global coordinate system.

The so-called  alignment matrix is one assembled from
smaller matrices that are projectors on subspaces. It lies at
the center of the Local Tangent Space Alignment method (LTSA)
for nonlinear dimensionality reduction recently proposed.
In this talk, we present the LTSA method through a spectral
analysis of the alignment matrix. Our analysis provides a
theoretical basis for the LTSA algorithm and leads to a
post-processing step that guarantees recovery of locally
isometric coordinates up to a rigid motion. For the purpose of
practical computations, we shall also discuss the first
nonzero eigenvalue and its geometric interpretation.