Clustering by Orthogonal Non-negative Matrix Factorization: A Sequential Non-convex Penalty Approach

The non-negative matrix factorization (NMF) model with an additional orthogonality constraint on one of the factor matrices, called the orthogonal NMF (ONMF), has been found to provide improved clustering performance over the K-means. The ONMF model is a challenging optimization problem due to the orthogonality constraint, and most of the existing methods directly deal with the constraint in its original form via various optimization techniques. In this paper, we propose an equivalent problem reformulation that transforms the orthogonality constraint into a set of norm-based non-convex equality constraints. We then apply a penalty approach to handle these non-convex constraints. The penalized formulation is smooth and has convex constraints, which is amenable to efficient computation. We analytically show that the penalized formulation will provide a feasible stationary point of the reformulated ONMF problem when the penalty is large. Numerical results show that the proposed method greatly outperforms the existing methods.