Maximum Variance Unfolding on Disjoint Manifolds

An assumption underlying much of machine learning is that observed data are often sampled from a manifold of much lower dimension than the data space itself. While linear methods such as PCA can often be used to perform dimensionality reduction, they fail to capture nonlinear relationships in the data, which are often present in natural datasets. Maximum variance unfolding (MVU) is an established and well-studied neighborhood graph-based method for nonlinear dimensionality reduction with the unique property of retaining strong local isometry. However, its applicability to real-world data is limited due to its dependence on the connectivity of the underlying neighborhood graph: in natural datasets, data are often irregularly sampled, multimodal, or lie on disjoint manifolds, giving rise to clusters of points that are distant in the data space. In this work, we present a method that extends MVU to the common case where data lie on disjoint manifolds. By embedding neighborhood graph components in parallel and later building component connections, our method decreases both computation time and memory requirements, even with a single processor. Furthermore, we identify two practical failure modes of MVU, which our method inherently addresses, resulting in improved performance with respect to standard metrics that assess the extent to which the local structure of the data is preserved.