Relative error bounds for nonnegative matrix factorization under a geometric assumption

Abstract

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. Furthermore, when combined with the classical alternating nonnegative least-squares algorithm, we show on synthetic examples that our proposed algorithm outperforms the standard algorithm based on multiplicative updates.