Locality constrained Graph Optimization for Dimensionality Reduction

Recently, graph-based dimensionality reduction methods have attracted much attention due to their widely applications in many practical tasks such as image classification and data clustering. However, an inappropriate graph which cannot accurately reflect the underlying structure and distribution of input data will dramatically deteriorate the performances of these methods. In this paper, we propose a novel algorithm termed Locality Constrained Graph Optimization Dimensionality Reduction (LC-GODR) to address the limitations of existing graph-based dimensionality reduction methods. Firstly, unlike most graph-based dimensionality reduction methods in which the graphs are constructed in advance and kept unchanged during dimensionality reduction, our LC-GODR combines the graph optimization and projection matrix learning into a joint framework. Therefore, the graph in the proposed algorithm can be adaptively updated during the procedure of dimensionality reduction. Secondly, through introducing the locality constraints into our LC-GODR, the local information of high-dimensional input data can be discovered and well preserved, which makes the proposed algorithm distinct from other graph optimization based dimensionality reduction methods. Moreover, an effective updating scheme is also provided to solve the proposed LC-GODR. Extensive experiments on two UCI and five image databases are conducted to demonstrate the effectiveness of our algorithm. The experimental results indicate that the proposed LC-GODR outperforms other related methods.