Robust (Semi) Nonnegative Graph Embedding

Nonnegative matrix factorization (NMF) has received considerable attention in image processing, computer vision, and patter recognition. An important variant of NMF is nonnegative graph embedding (NGE), which encodes the statistical or geometric information of data in the process of matrix factorization. The NGE offers a general framework for unsupervised/supervised settings. However, NGE-like algorithms often suffer from noisy data, unreliable graphs, and noisy labels, which are commonly encountered in real-world applications. To address these issues, in this paper, we first propose a robust nonnegative graph embedding (RNGE) framework, where the joint sparsity in both graph embedding and data reconstruction endues robustness to undesirable noises. Next, we present a robust seminonnegative graph embedding (RsNGE) framework, which only constrains the coefficient matrix to be nonnegative while places no constraint on the base matrix. This extends the applicable range of RNGE to data which are not nonnegative and endows more discriminative power of the learnt base matrix. The RNGE/RsNGE provides a general formulation such that all the algorithms unified within the graph embedding framework can be easily extended to obtain their robust nonnegative/seminonnegative solutions. Further, we develop elegant multiplicative updating solutions that can solve RNGE/RsNGE efficiently and offer a rigorous convergence analysis. We conduct extensive experiments on four real-world data sets and compare the proposed RNGE/RsNGE to other representative NMF variants and data factorization methods. The experimental results demonstrate the robustness and effectiveness of the proposed approaches.