Adaptive graph orthogonal discriminant embedding: an improved graph embedding method

Graph embedding is a popular graph based dimensionality reduction framework, and it consists of two successive steps, i.e., graph construction and embedding. The traditional graph construction methods such as \(k\)-nearest-neighbor (k-NN) and \(\varepsilon\)-ball suffer from the difficulty in parameter selection and are also sensitive to noises. On the other hand, the property of embedding projection is not fully explored by many methods. In this paper, we explicitly investigate these two steps and propose three adaptive graph orthogonal discriminant embedding techniques (termed as AGODE-gs, AGODE-dl and AGODE-tr) for dimensionality reduction, and their differences lie in the way of orthogonalization. In our proposed methods, both the intra-class adjacency graph and the inter-class repulsion graph are constructed by a \(\ell_{2}\)-norm regularized least square, and an orthogonal constraint between the projection vectors is then imposed. The time and space complexity of the proposed methods are also analyzed in detail. We further show that the proposed methods are computationally more efficient than those \(\ell_{1}\)-norm based graph construction methods. Extensive experiments on four face databases (ORL, Yale, CUM-PIE and Extended YaleB) verify the effectiveness and efficiency of the proposed methods with encouraging results.