Search for a command to run...
Dimensionality reduction and manifold learning techniques attempt to recover a lower‐dimensional submanifold from the data as encoded in high dimensions. Many techniques, linear or non‐linear, have been introduced in the literature. Standard methods, such as Isomap and local linear embedding, map the high‐dimensional data points into a low dimension so as to globally minimize a so‐called energy function, which measures the mismatch between the precise geometry in high dimensions and the approximate geometry in low dimensions. However, the local effects of such minimizations are often unpredictable, because the energy minimization algorithms are global in nature. In contrast to these methods, the Spanifold algorithm of this paper constructs a tree on the manifold and flattens the manifold in such a way as to approximately preserve pairwise distance relationships within the tree. The vertices of this tree are the data points, and the edges of the tree form a subset of the edges of the nearest‐neighbour graph on the data. In addition, the pairwise distances between data points close to the root of the tree undergo minimal distortion as the data are flattened. This allows the user to design the flattening algorithm so as to approximately preserve neighbour relationships in any chosen local region of the data. Copyright © 2015 John Wiley & Sons, Ltd.