Efficient locally linear embeddings of imperfect manifolds

In this paper, we explore the capabilities of a recently proposed method for non-linear dimensionality reduction and visualization called Locally Linear Embedding (LLE). LLE is proposed as an alternative to the traditional approaches. Its ability to deal with large sizes of high dimensional data and non-iterative way to find the embeddings make it more and more attractive to several researchers. All the studies which investigated and experimented this approach have concluded that LLE is a robust and efficient algorithm when the data lie on a smooth and well-sampled single manifold. None explored the behavior of the algorithm when the data include some noise (or outliers). Here, we show theoretically and empirically that LLE is significantly sensitive to the presence of a few outliers. Then we propose a robust extension to tackle this problem. Further, we investigate the behavior of the LLE algorithm in cases of disjoint manifolds, demonstrate the lack of single global coordinate system and discuss some alternatives.