The Diagonalized Newton Algorithm for Nonnegative Matrix Factorization
This work addresses a computational bottleneck for researchers and practitioners using NMF in domains like text mining and image processing, offering an incremental improvement over existing methods.
The paper tackled the problem of slow convergence in non-negative matrix factorization (NMF) by proposing a diagonalized Newton algorithm (DNA), which achieved faster convergence while maintaining simplicity and suitability for high-rank problems, with results showing a substantial speed-up on modern hardware.
Non-negative matrix factorization (NMF) has become a popular machine learning approach to many problems in text mining, speech and image processing, bio-informatics and seismic data analysis to name a few. In NMF, a matrix of non-negative data is approximated by the low-rank product of two matrices with non-negative entries. In this paper, the approximation quality is measured by the Kullback-Leibler divergence between the data and its low-rank reconstruction. The existence of the simple multiplicative update (MU) algorithm for computing the matrix factors has contributed to the success of NMF. Despite the availability of algorithms showing faster convergence, MU remains popular due to its simplicity. In this paper, a diagonalized Newton algorithm (DNA) is proposed showing faster convergence while the implementation remains simple and suitable for high-rank problems. The DNA algorithm is applied to various publicly available data sets, showing a substantial speed-up on modern hardware.