Max-Margin Semi-NMF

In this paper, we propose a maximum-margin framework for classification using Non-negative Matrix Factorization. In contrast to previous approaches where the classification and matrix factorization are separated, we incorporate the maximum margin constraints within the NMF formuation i.e. we solve for a base matrix that maximizes the margin of the classifier in the low dimensional feature space. This results in a non-convex constrained optimization problem with respect to the bases, the projection coefficients and the separating hyperplane, which we propose to solve in an iterative way, solving at each iteration a set of convex sub-problems with respect to subsets of the unknown variables. The resulting basis matrix is used to extract features that maximize the margin of the resulting classifier. The performance of the proposed algorithm is evaluated on several publicly available datasets where it is shown to consistently outperform Discriminative NMF and SVM classifiers that use features extracted by semi-NMF.