Discriminant Hyper-Laplacian Projections and its scalable extension for dimensionality reduction

Discriminant Locality Preserving Projections (DLPP) is one of the most influential supervised subspace learning algorithms that consider both discriminative and geometric (manifold) information. There is an obvious drawback of DLPP that it only considers the pairwise geometric relationship of samples. However, in many real-world issues, relationships among the samples are often more complex than pairwise. Naively squeezing the complex into pairwise ones will inevitably lead to loss of some information, which are crucial for classification and clustering. We address this issue via using the Hyper-Laplacian instead of the regular Laplacian in DLPP, which only can depict the pairwise relationship. This new DLPP algorithm is exactly a generalization of DLPP and we name it Discriminant Hyper-Laplacian Projection (DHLP). In order to make DHLP can be feasibly applied to big data dimensionality reduction, we adopt the spectral regression framework to reduce the computational complexity of DHLP from cubic-time to linear-time. We named this new DHLP algorithm Scalable Discriminant Hyper-Laplacian Projections (SDHLP). Six popular visual databases are adopted for validating our work. The results not only demonstrate the superiorities of DHLP and SDHLP in comparison with the state-of-the-art algorithms but also demonstrate the efficiency improvement of SDHLP over DHLP.