The Why and How of Nonnegative Matrix Factorization
This work addresses a computational bottleneck for researchers and practitioners using NMF in applications like image processing and text mining, but it is incremental as it builds on existing NMF methods.
The paper tackles the problem of solving nonnegative matrix factorization (NMF), which is NP-hard in general, by reviewing standard algorithms and presenting a subclass called near-separable NMF that can be solved efficiently in polynomial time, even with noise.
Nonnegative matrix factorization (NMF) has become a widely used tool for the analysis of high-dimensional data as it automatically extracts sparse and meaningful features from a set of nonnegative data vectors. We first illustrate this property of NMF on three applications, in image processing, text mining and hyperspectral imaging --this is the why. Then we address the problem of solving NMF, which is NP-hard in general. We review some standard NMF algorithms, and also present a recent subclass of NMF problems, referred to as near-separable NMF, that can be solved efficiently (that is, in polynomial time), even in the presence of noise --this is the how. Finally, we briefly describe some problems in mathematics and computer science closely related to NMF via the nonnegative rank.