A multilevel approach for nonnegative matrix factorization

Nonnegative matrix factorization (NMF), the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices, has been shown to be useful in many applications, such as text mining, image processing, and computational biology. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their initial convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. Several simple multilevel strategies are described and are experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets.