Analysis of an alignment algorithm for nonlinear dimensionality reduction

Qiang Ye, Hongyuan Zha, Ren Cang Li

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)873-885
Number of pages13
JournalBIT Numerical Mathematics
Volume47
Issue number4
DOIs
StatePublished - Dec 2007

Bibliographical note

Funding Information:
★★ Q. Ye was partially supported by the NSF Grant DMS-0411502. H. Zha was partially supported by NSF grants DMS-0311800 and DMS-0405681. R. Li was partially supported by NSF CAREER award CCR-9875201 and by NSF Grant DMS-0510664.

Keywords

  • Alignment algorithm
  • Dimensionality reduction
  • Manifold learning

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Analysis of an alignment algorithm for nonlinear dimensionality reduction'. Together they form a unique fingerprint.

Cite this