Non-negative graph embedding

We introduce a general formulation, called non-negative graph embedding, for non-negative data decomposition by integrating the characteristics of both intrinsic and penalty graphs [17]. In the past, such a decomposition was ob-tained mostly in an unsupervised manner, such as Non-negative Matrix Factorization (NMF) and its variants, and hence unnecessary to be powerful at classification. In this work, the non-negative data decomposition is stud-ied in a unified way applicable for both unsupervised and supervised/semi-supervised configurations. The ultimate data decomposition is separated into two parts, which sep-aratively preserve the similarities measured by the intrinsic and penalty graphs, and together minimize the data recon-struction error. An iterative procedure is derived for such a purpose, and the algorithmic non-negativity is guaranteed by the non-negative property of the inverse of any M-matrix. Extensive experiments compared with NMF and conven-tional solutions for graph embedding demonstrate the al-gorithmic properties in sparsity, classification power, and robustness to image occlusions. 1