Incremental Spectral Embedding Methods In Manifold Learning

Dimensionality reduction is a novel research direction, which integrates the knowl-edge from mathematics and computer science. It mainly focuses on the problem of repre-senting the original high dimensional data in a low dimensional space and discovering theintrinsic structure. Especially, manifold learning methods make a great progress in un-derstanding the structure of multidimensional patterns. Most of these methods, however,operate in a batch mode and cannot be effectively applied when data samples are collectedsequentially. Therefore,incrementalmanifoldlearninghasappearedinresearchers'sights.Under the background of incremental learning, this thesis has exclusively studiedout-of-sample extensions of spectral embedding algorithms in manifold learning. Moreconcretely, the main contributions of this thesis can be summarized into two aspects.On the one hand, a general incremental framework is proposed for spectral embed-ding algorithms, a significant category of manifold learning methods. Not only does thisframework unify several contributions in incremental learning, but also it extends the ex-isting methods to be able to deal with the cases when two or more observations comesimultaneously, conquering the limitation of tackling only one sample per time. Mean-while,wepresenttheconvergentconditionsofincrementalspectralembeddingalgorithmsand analyze their convergence performance.On the other hand, two novel incremental algorithms, consisting of the incrementalHLLE algorithm and the incremental LSE algorithm, are proposed by utilizing the generalframework as a tool. The complexity of computations of these two algorithms is theoret-ically analyzed. Compared with the batch methods, the two incremental methods show adesirable gift in terms of computational costs. Moreover, the efficiency and the accuracyof the proposed algorithms are evaluated on both synthetic and image dataset. All thenumerical simulations are designed from two views: one is dimensionality reduction andthe other is pattern classification based on reduced representation of original data.Finally, we sum up the research results in this thesis and describe several directionsof further research in the fields.