Self-Organizing Isometric Embedding

Most algorithms of nonlinear dimensionality reduction suffer some flaws in common. First, these algorithms need to solve large-scale eigenvalues problems or some variation of eigenvalues problems, which is usually of quadratic complexity of time. The quadratic complexity limits the applicability of algorithms in the case of large-size sampling sets, which are very prevalent in the applications of real world, e.g., texts clustering, images recognitions, biological information and so on. Second, current algorithms are global and analytic, which are often sensitive to noise and disturbed by ill-conditioned matrix. To overcome the above problems, a novel self-organizing nonlinear dimensionality reduction algorithm: SIE (self-organizing isometric embedding) is proposed. The time complexity of SIE is O(NlogN)， which can bring a N/logN speedup against most current algorithms. Besides, the main computing procedure of SIE is based on locally self-organizing scheme, which improves the robustness of the algorithm remarkably and circumvents the trouble introduced by ill-conditioned matrix. The simulations demonstrate that the reconstructing quality of SIE is as optimal as the best global algorithm in the case of clean sampling sets and superior to global algorithms prominently in the case of noisy sampling sets.