Linear Graph Embedding Algorithms

This thesis studies the linear extension of graph embedding. Both graphs and manifolds can be embedded in Euclidean space, the current manifold learning algorithms and many of the classical dimension reduction, feature extraction methods, can characteristics through Spectral Graph Theory.Many dimension reduction algorithms, such as PCA, LDA, ISOMAP, LLE, LE, despite the different motivations of these algorithms, could be unified by a general formulation known as graph embedding within a common framework. In graph embedding, each algorithm can be considered as the direct graph embedding or its linear/kernel/tensor extension of a specific intrinsic graph that describes certain desired statistical or geometric properties of a data set, with constraints from scale normalization or a penalty graph that characterizes a statistical or geometric property that should be avoided.In this thesis, we introduce our work on linear extension of graph embedding:Direct Linear Graph Embedding algorithm:In small sample size problem applications, the traditional linear graph embedding algorithms need an PCA preprocessing step to avoid the matrix singularity problem, which may lose some discriminating information. We propose a direct linear graph embedding algorithm can extract features directly from the data set without PCA preprocessing.The direct linear graph embedding algorithm based on Local Feature Analysis: In general, the local structures of the images reflect some inherent characteristics of the images, we proposed an effective algorithm of image recognition which based Local Feature Analysis and the direct linear graph embedding algorithm.Orthogonal direct linear graph embedding:linear graph embedding algorithms are usually non-orthogonal, we propose the orthogonal least squares linear graph embedding algorithm directly.Regularization direct linear graph embedding algorithm:We proposed regularization direct linear graph embedding algorithm, without increasing the algorithm complexity, which can improve the performance of the algorithm and the generalization ability.Linear graph embedding algorithm based on Image Euclidean Distance:We propose that Image Euclidean Distance instead of vector Euclidean distance to describe the similarity between the sample points, consider the geometric information between pixels of the images.Experimental results performed on some typical databases demonstrated the effectiveness and robustness of our proposed algorithms.