Connectionists: two papers and one software for NMF

[Chih-Jen Lin]

Dear Colleagues,

We announce two papers and one software package
for Nonnegative Matrix Factorization (NMF).

Paper: Projected gradient methods for non-negative matrix
factorization. To appear in Neural Computation 2007.
http://www.csie.ntu.edu.tw/~cjlin/papers/pgradnmf.pdf

Abstract: 
Non-negative matrix factorization (NMF) can be formulated as a
minimization problem with bound constraints.  Although
bound-constrained optimization has been studied extensively in both
theory and practice, so far no study has formally applied its
techniques to NMF.  In this paper, we propose two projected gradient
methods for NMF. The proposed methods exhibit strong optimization
properties. We discuss efficient implementations and demonstrate that
one of the proposed methods converges faster than the popular
multiplicative update approach.  A simple MATLAB code is also
provided.

Software:
An fast implementation of the proposed method in the above paper is at
http://www.csie.ntu.edu.tw/~cjlin/nmf

Paper: On the convergence of multiplicative update algorithms for
non-negative matrix factorization. To appear in IEEE TNN 2007
http://www.csie.ntu.edu.tw/~cjlin/papers/multconv.pdf

abstract: Non-negative matrix factorization (NMF) is useful to find
basis information of non-negative data. Currently, multiplicative
updates are a simple and popular way to find the factorization.
However, for the common NMF approach of minimizing the Euclidean
distance between approximate and true values, no proof has shown that
that multiplicative updates converge to a stationary point of the NMF
optimization problem. Stationarity is important as it is a necessary
condition of a local minimum. This paper discusses the difficulty of
proving the convergence. We propose slight modifications of existing
updates and prove their convergence.  Techniques invented in this
paper may be applied to prove the convergence for other
bound-constrained optimization problems.

Your comments are very welcome.

Best regards,
Chih-Jen Lin
Dept. of Computer Science
National Taiwan Univ.