Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumption
This work addresses computational bottlenecks in NMF for applications like image and text analysis, offering an incremental improvement through a novel initialization method.
The paper tackles the problem of improving the speed and accuracy of nonnegative matrix factorization (NMF) by proposing a geometric assumption that enables exact clustering and rank-one NMFs, resulting in faster speeds with comparable relative errors to classical methods.
We propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization (NMF). The algorithm we propose first uses the geometric assumption to obtain an exact clustering of the columns of the data matrix; subsequently, it employs several rank-one NMFs to obtain the final decomposition. When applied to data matrices generated from our statistical model, we observe that our proposed algorithm produces factor matrices with comparable relative errors vis-à-vis classical NMF algorithms but with much faster speeds. On face image and hyperspectral imaging datasets, we demonstrate that our algorithm provides an excellent initialization for applying other NMF algorithms at a low computational cost. Finally, we show on face and text datasets that the combinations of our algorithm and several classical NMF algorithms outperform other algorithms in terms of clustering performance.