Efficient Nonnegative Matrix Factorization via projected Newton method

Nonnegative Matrix Factorization (NMF) is a popular decomposition technique in pattern analysis, document clustering, image processing and related fields. In this paper, we propose a fast NMF algorithm via Projected Newton Method (PNM). First, we propose PNM to efficiently solve a nonnegative least squares problem, which achieves a quadratic convergence rate under appropriate assumptions. Second, in the framework of an alternating optimization method, we adopt PNM as an essential subroutine to efficiently solve the NMF problem. Moreover, by exploiting the low rank assumption of NMF, we make PNM very suitable for solving NMF efficiently. Empirical studies on both synthetic and real-world (text and image) data demonstrate that PNM is quite efficient to solve NMF compared with several state of the art algorithms.

► We propose a fast Nonnegative Matrix Factorization (NMF) algorithm via projected Newton method (PNM).
► We propose PNM to solve a nonnegative least squares problem, achieving a quadratic convergence rate under appropriate assumptions.
► PNM, as an essential subroutine, efficiently solve the NMF problem.
► We exploit the low rank assumption of NMF and propose efficient implementations for NMF problem.
► PNM achieves a faster convergence speed compared with state of the art algorithms.