Unified Development of Multiplicative Algorithms for Linear and Quadratic Nonnegative Matrix Factorization
Authors:
- 17 October 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 22 (12) , 1878-1891
Abstract
Multiplicative updates have been widely used in approximative nonnegative matrix factorization (NMF) optimization because they are convenient to deploy. Their convergence proof is usually based on the minimization of an auxiliary upper-bounding function, the construction of which however remains specific and only available for limited types of dissimilarity measures. Here we make significant progress in developing convergent multiplicative algorithms for NMF. First, we propose a general approach to derive the auxiliary function for a wide variety of NMF problems, as long as the approximation objective can be expressed as a finite sum of monomials with real exponents. Multiplicative algorithms with theoretical guarantee of monotonically decreasing objective function sequence can thus be obtained. The solutions of NMF based on most commonly used dissimilarity measures such as α - and β-divergence as well as many other more comprehensive divergences can be derived by the new unified principle. Second, our method is extended to a nonseparable case that includes e.g., γ-divergence and Rényi divergence. Third, we develop multiplicative algorithms for NMF using second-order approximative factorizations, in which each factorizing matrix may appear twice. Preliminary numerical experiments demonstrate that the multiplicative algorithms developed using the proposed procedure can achieve satisfactory Karush-Kuhn-Tucker optimality. We also demonstrate NMF problems where algorithms by the conventional method fail to guarantee descent at each iteration but those by our principle are immune to such violation.Keywords
This publication has 36 references indexed in Scilit:
- Stability Analysis of Multiplicative Update Algorithms and Application to Nonnegative Matrix FactorizationIEEE Transactions on Neural Networks, 2010
- Non-negative matrix factorization for parameter estimation in hidden Markov models2010
- Linear and Nonlinear Projective Nonnegative Matrix FactorizationIEEE Transactions on Neural Networks, 2010
- Nonnegative Matrix Factorization for Combinatorial Optimization: Spectral Clustering, Graph Matching, and Clique Finding2008
- PROJECTIVE NON-NEGATIVE MATRIX FACTORIZATION WITH APPLICATIONS TO FACIAL IMAGE PROCESSINGInternational Journal of Pattern Recognition and Artificial Intelligence, 2007
- On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix FactorizationIEEE Transactions on Neural Networks, 2007
- Initialization enhancer for non-negative matrix factorizationEngineering Applications of Artificial Intelligence, 2007
- Orthogonal nonnegative matrix t-factorizations for clustering2006
- Discovering hierarchical speech features using convolutional non-negative matrix factorization2004
- Parameterisation of a stochastic model for human face identification2002