Intersecting Faces: Non-negative Matrix Factorization With New Guarantees
This work addresses the challenge of developing provably correct algorithms for a broader class of NMF problems, which is incremental but important for applications in science and engineering.
The authors tackled the problem of non-negative matrix factorization (NMF) by introducing subset-separable NMF, a generalization of separable NMF, and developed the Face-Intersect algorithm that provably and efficiently solves it under natural conditions with robustness to small noise, showing empirical outperformance over state-of-the-art methods in simulations.
Non-negative matrix factorization (NMF) is a natural model of admixture and is widely used in science and engineering. A plethora of algorithms have been developed to tackle NMF, but due to the non-convex nature of the problem, there is little guarantee on how well these methods work. Recently a surge of research have focused on a very restricted class of NMFs, called separable NMF, where provably correct algorithms have been developed. In this paper, we propose the notion of subset-separable NMF, which substantially generalizes the property of separability. We show that subset-separability is a natural necessary condition for the factorization to be unique or to have minimum volume. We developed the Face-Intersect algorithm which provably and efficiently solves subset-separable NMF under natural conditions, and we prove that our algorithm is robust to small noise. We explored the performance of Face-Intersect on simulations and discuss settings where it empirically outperformed the state-of-art methods. Our work is a step towards finding provably correct algorithms that solve large classes of NMF problems.