Manifold-respecting discriminant nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is an unsupervised learning method for low-rank approximation of nonnegative data, where the target matrix is approximated by a product of two nonnegative factor matrices. Two important ingredients are missing in the standard NMF methods: (1) discriminant analysis with label information; (2) geometric structure (manifold) in the data. Most of the existing variants of NMF incorporate one of these ingredients into the factorization. In this paper, we present a variation of NMF which is equipped with both these ingredients, such that the data manifold is respected and label information is incorporated into the NMF. To this end, we regularize NMF by intra-class and inter-class k-nearest neighbor (k-NN) graphs, leading to NMF-kNN, where we minimize the approximation error while contracting intra-class neighborhoods and expanding inter-class neighborhoods in the decomposition. We develop simple multiplicative updates for NMF-kNN and present monotonic convergence results. Experiments on several benchmark face and document datasets confirm the useful behavior of our proposed method in the task of feature extraction. (C) 2011 Elsevier B.V. All rights reserved.