Parallel Nonnegative Matrix Factorization Based on Newton Iteration with Improved Convergence Behavior

The Nonnegative Matrix Factorization (NMF) approximates a large nonnegative matrix as a product of two significantly smaller nonnegative matrices. Because of the nonnegativity constraints, all existing methods for NMF are iterative. Newton-type methods promise good convergence rate and can also be parallelized very well because Newton iterations can be performed in parallel without exchanging data between processes. However, previous attempts have revealed problematic convergence behavior, limiting their efficiency. Therefore, we combine Karush-Kuhn-Tucker (KKT) conditions and a reflective technique for constraint handling, take care of global convergence by backtracking line search, and apply a modified target function in order to satisfy KKT inequalities. By executing only few Newton iterations per outer iteration, the algorithm is turned into a so-called inexact method. Experiments show that this leads to faster convergence in the sequential as well as in the parallel case. Although shorter Newton phases increase the relative parallel communication overhead, speedups are still satisfactory.