Nonlinear Dimensionality Reduction by Locally Linear Inlaying

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.