Analysis of an alignment algorithm for nonlinear dimensionality reduction

The goal of dimensionality reduction or manifold learning for a given set of high-dimensional data points, is to find a low-dimensional parametrization for them. Usually it is easy to carry out this parametrization process within a small region to produce a collection of local coordinate systems. Alignment is the process to stitch those local systems together to produce a global coordinate system and is done through the computation of a partial eigendecomposition of a so-called alignment matrix. In this paper, we present an analysis of the alignment process, giving conditions under which the null space of the alignment matrix recovers the global coordinate system up to an affine transformation. We also propose a post-processing step that can determine the global coordinate system up to a rigid motion. This in turn shows that Local Tangent Space Alignment method (LTSA) can recover a locally isometric embedding up to a rigid motion. AMS subject classification (2000)  65F15, 62H30, 15A18