A Study On Manifold Learning Algorithms

Traditional nonlinear dimensionality reduction algorithms e.g. ISOMAP LLE SIE works in batch mode. It means that al data points need to be available during embedding. When data points arrive sequentially, batch mode methods are computationally expensive. At the same time, the traditional dimensionality reduction algorithms need to solve large-scale eigenvalues problems or compute geodesic distances, both is of quadratic complexity of time. The quadratic complexity limits the applicability of algorithms in the case of large-size sampling sets.In order to process incremental data points, we propose AISIE algorithm. Assuming that sampling point of underlying manifold and its adaptive neighbors can preserve the principal directions of the regions that they reside on, our algorithm need only update the geodesic distances between anchors and all other points, as well as distances between neighbors of incremental points and all other points when a new point arrives. Under the above assumption, our algorithm can realize an approximate linear time complexity embedding of incremental points and effectively tradeoff embedding precision and time cost.We propose LLI algorithm, obtain embeddings without solving large-scale eigenvalues problems or computing geodesic distances. By solving an optimization problem LLI can inlay two embeddings of linear regions together. Also propose a method to divide the nonlinear manifold into local linear regions. The complexity of LLI is related to the number of common points between neighborhood regions. When (d is embedding dimension) the complexity to inlay two regions is O( ). Together with manifold division the complexity to obtain embeddings is O(T*n*m*log(m)+m*n+ k*n+m*dg).