NMF revisited: New uniqueness results and algorithms

Non-negative matrix factorization (NMF) has found numerous applications, due to its ability to provide interpretable decompositions. Perhaps surprisingly, existing results regarding its uniqueness properties are rather limited, and there is much room for improvement in terms of algorithms as well. Uniqueness and computational aspects of NMF are revisited here from a geometrical point of view. Both symmetric and asymmetric NMF are considered, the former being tantamount to element-wise non-negative square-root factorization of positive semidefinite matrices. New and insightful uniqueness results are derived, e.g., it is shown that a sufficient condition for uniqueness is that the conic hull of the latent factors is a superset of a particular second-order cone. Checking this is shown to be NP-complete; yet it offers insights on latent sparsity, as is also shown in a new necessary condition, to a smaller extent. On the computational side, a new efficient algorithm for symmetric NMF is proposed which uses Procrustes rotations. Simulation results show promising performance with respect to the state-of-art. The new algorithm is also applied to a clustering problem for co-authorship data, yielding meaningful and interpretable results.