Nonlinear embedding preserving multiple local-linearities

Locally linear embedding (LLE) is one of the effective and efficient algorithms for nonlinear dimensionality reduction. This paper discusses the stability of LLE, focusing on the optimal weights for extracting local linearity behind the considered manifold. It is proven that there are multiple sets of weights that are approximately optimal and can be used to improve the stability of LLE. A new algorithm using multiple weights is then proposed, together with techniques for constructing multiple weights. This algorithm is called as nonlinear embedding preserving multiple local-linearities (NEML). NEML improves the preservation of local linearity and is more stable than LLE. A short analysis for NEML is also given for isometric manifolds. NEML is compared with the local tangent space alignment (LTSA) in methodology since both of them adopt multiple local constraints. Numerical examples are given to show the improvement and efficiency of NEML. (C) 2009 Elsevier Ltd. All rights reserved.