Projective nonnegative graph embedding

Abstract

We present in this paper a general formulation for nonnegative data factorization, called projective nonnegative graph embedding (PNGE), which 1) explicitly decomposes the data into two nonnegative components favoring the characteristics encoded by the so-called intrinsic and penalty graphs , respectively, and 2) explicitly describes how to transform each new testing sample into its low-dimensional nonnegative representation. In the past, such a nonnegative decomposition was often obtained for the training samples only, e.g., nonnegative matrix factorization (NMF) and its variants, nonnegative graph embedding (NGE) and its refined version multiplicative nonnegative graph embedding (MNGE). Those conventional approaches for out-of-sample extension either suffer from the high computational cost or violate the basic nonnegative assumption. In this work, PNGE offers a unified solution to out-of-sample extension problem, and the nonnegative coefficient vector of each datum is assumed to be projected from its original feature representation with a universal nonnegative transformation matrix. A convergency provable multiplicative nonnegative updating rule is then derived to learn the basis matrix and transformation matrix. Extensive experiments compared with the state-of-the-art algorithms on nonnegative data factorization demonstrate the algorithmic properties in convergency, sparsity, and classification power.