  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-\`a-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.
