Naiyang Guan (管乃洋), 国防科技大学


Non-negative matrix factorization and its optimization


This tutorial presents the non-negative matrix factorization (NMF) method and an efficient NMF solver called NeNMF. NMF is a novel dimension reduction method which has been widely used in pattern recognition, data mining and information retrieval since the end of the twentieth century. Distinguished from other matrix decomposition methods such as singular value decomposition and Eigen-value decomposition, NMF focuses on processing non-negative matrices and approximates a given non-negative matrix by the product of two lower-rank non-negative matrices. Since NMF represents an example by an additive combination of features, it yields natural sparse and parts-based representation. Such data representation is consistent with the physiological and psychological evidence in human brain, and usually suppresses the noises in data. By proving the convexity of each sub-problem of NMF, we applied the optimal gradient method to alternatively optimizing the matrix factors. The NMF optimization algorithms have received many attentions. There exist many methods such as multiplicative update rule, projected gradient, quasi-Newton, and active set method. However, they suffer from one or more following drawbacks: (1) slow convergence; (2) high computational complexity; and (3) numerical instability. Therefore, how to efficiently optimize NMF is still an open problem. This thesis proves that each sub-problem of NMF is convex and the gradient is Lipschitz continuous, and thus the optimal gradient method can be directly applied to optimize each matrix factor at the optimal convergence rate O(1/k^2) without line search. Similarly, by proving the convexities of both sub-problems of NMF, we proposed an efficient NMF optimization algorithm based on OGM. Experimental results on both synthetic and real-world datasets show that NeNMF is much faster than the state-of-the-art NMF solvers. In this tutorial, I also want to other optimization methods for NMF and critical theoretical issues on the NMF optimization problem.

« Back