Adaptive multiplicative updates for quadratic nonnegative matrix factorization

• This paper presents a novel adaptive multiplicative update scheme for Quadratic Nonnegative Matrix Factorization (QNMF).
• The proposed adaptive algorithm can significantly speed up the convergence while still maintaining the monotonicity of updates.
• Extensive empirical results demonstrate that our new method is effective in various QNMF applications on both synthetic and real-world datasets.
• The proposed adaptive exponent technique can be easily extended to other fixed-point algorithms that use multiplicative updates as well.

In Nonnegative Matrix Factorization (NMF), a nonnegative matrix is approximated by a product of lower-rank factorizing matrices. Quadratic Nonnegative Matrix Factorization (QNMF) is a new class of NMF methods where some factorizing matrices occur twice in the approximation. QNMF finds its applications in graph partition, bi-clustering, graph matching, etc. However, the original QNMF algorithms employ constant multiplicative update rules and thus have mediocre convergence speed. Here we propose an adaptive multiplicative algorithm for QNMF which is not only theoretically convergent but also significantly faster than the original implementation. An adaptive exponent scheme has been adopted for our method instead of the old constant ones, which enables larger learning steps for improved efficiency. The proposed method is general and thus can be applied to QNMF with a variety of factorization forms and with the most commonly used approximation error measures. We have performed extensive experiments, where the results demonstrate that the new method is effective in various QNMF applications on both synthetic and real-world datasets.