Name
Title | ||
|---|---|---|
Unified development of multiplicative algorithms for linear and quadratic nonnegative matrix factorization. |
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TNN.2011.2170094 | IEEE Transactions on Neural Networks |
Keywords | Field | DocType |
nmf problem,α-divergence,unified development,dissimilarity measure,nonnegative,β-divergence,linear nonnegative matrix factorization,multiplicative updates,quadratic nonnegative matrix factorization,multiplicative algorithm,divergence,auxiliary upper-bounding function,multiplicative algorithms,nyi divergence,function approximation,objective function sequence,convergent multiplicative algorithm,auxiliary function,multiplicative,optimization,convergence of numerical methods,karush-kuhn- tucker optimality,matrix decomposition,matrix factorization,minimisation,second-order approximative factorization,convergence proof,comprehensive divergence,second order approximation,approximation algorithms,objective function,minimization,upper bound,approximation error,polynomials,convergence,karush kuhn tucker,nonnegative matrix factorization | Monotonic function,Approximation algorithm,Polynomial,Function approximation,Multiplicative function,Computer science,Matrix decomposition,Algorithm,Auxiliary function,Non-negative matrix factorization | Journal |
Volume | Issue | ISSN |
22 | 12 | 1941-0093 |
Citations | PageRank | References |
29 | 1.17 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhirong Yang | 1 | 289 | 17.27 |
| Erkki Oja | 2 | 6701 | 797.08 |