Skip to main content

Intersecting faces: Non-negative matrix factorization with new guarantees

Publication ,  Conference
Ge, R; Zou, J
Published in: 32nd International Conference on Machine Learning, ICML 2015
January 1, 2015

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 Scholars

Published In

32nd International Conference on Machine Learning, ICML 2015

ISBN

9781510810587

Publication Date

January 1, 2015

Volume

3

Start / End Page

2285 / 2293
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ge, R., & Zou, J. (2015). Intersecting faces: Non-negative matrix factorization with new guarantees. In 32nd International Conference on Machine Learning, ICML 2015 (Vol. 3, pp. 2285–2293).
Ge, R., and J. Zou. “Intersecting faces: Non-negative matrix factorization with new guarantees.” In 32nd International Conference on Machine Learning, ICML 2015, 3:2285–93, 2015.
Ge R, Zou J. Intersecting faces: Non-negative matrix factorization with new guarantees. In: 32nd International Conference on Machine Learning, ICML 2015. 2015. p. 2285–93.
Ge, R., and J. Zou. “Intersecting faces: Non-negative matrix factorization with new guarantees.” 32nd International Conference on Machine Learning, ICML 2015, vol. 3, 2015, pp. 2285–93.
Ge R, Zou J. Intersecting faces: Non-negative matrix factorization with new guarantees. 32nd International Conference on Machine Learning, ICML 2015. 2015. p. 2285–2293.

Published In

32nd International Conference on Machine Learning, ICML 2015

ISBN

9781510810587

Publication Date

January 1, 2015

Volume

3

Start / End Page

2285 / 2293