When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?

Donoho, David L.; Stodden, Victoria C.

We interpret non-negative matrix factorization geometrically, as the problem of finding a simplicial cone which contains a cloud of data points and which is contained in the positive orthant. We show that under certain conditions, basically requiring that some of the data are spread across the faces of the positive orthant, there is a unique such simplicial cone. We give examples of synthetic image articulation databases which obey these conditions; these require separated support and factorial sampling. For such databases there is a generative model in terms of "parts" and NMF correctly identifies the "parts". We show that our theoretical results are predictive of the performance of published NMF code, by running the published algorithms on one of our synthetic image articulation databases.



Also Published In

Advances in neural information processing systems 16: proceedings of the 2003 conference
MIT Press

More About This Work

Academic Units
Published Here
October 11, 2011