Intersecting faces: Non-negative matrix factorization with new guarantees

Conference Paper

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.

Duke Authors

Cited Authors

  • Ge, R; Zou, J

Published Date

  • January 1, 2015

Published In

  • 32nd International Conference on Machine Learning, Icml 2015

Volume / Issue

  • 3 /

Start / End Page

  • 2285 - 2293

International Standard Book Number 13 (ISBN-13)

  • 9781510810587

Citation Source

  • Scopus