Nonlinear dimensionality reduction by locally linear inlaying

Yuexian Hou, Peng Zhang, Xingxing Xu, Xiaowei Zhang, Wenjie Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)

Abstract

High-dimensional data is involved in many fields of information processing. However, sometimes, the intrinsic structures of these data can be described by a few degrees of freedom. To discover these degrees of freedom or the low-dimensional nonlinear manifold underlying a high-dimensional space, many manifold learning algorithms have been proposed. Here we describe a novel algorithm, locally linear inlaying (LLI), which combines simple geometric intuitions and rigorously established optimality to compute the global embedding of a nonlinear manifold. Using a divide-and-conquer strategy, LLI gains some advantages in itself. First, its time complexity is linear in the number of data points, and hence LLI can be implemented efficiently. Second, LLI overcomes problems caused by the nonuniform sample distribution. Third, unlike existing algorithms such as isometric feature mapping (Isomap), local tangent space alignment (LTSA), and locally linear coordination (LLC), LLI is robust to noise. In addition, to evaluate the embedding results quantitatively, two criteria based on information theory and Kolmogorov complexity theory, respectively, are proposed. Furthermore, we demonstrated the efficiency and effectiveness of our proposal by synthetic and real-world data sets.
Original languageEnglish
Pages (from-to)300-315
Number of pages16
JournalIEEE Transactions on Neural Networks
Volume20
Issue number2
DOIs
Publication statusPublished - 19 Jan 2009

Keywords

  • Isometric feature mapping
  • Local tangent space alignment
  • Locally linear inlaying (LLI)
  • Manifold learning
  • Nonlinear dimensionality reduction
  • Robustness

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this