Title: Acceleration of iterative methods for nonnegative matrix factorization
Authors: Michio Sakakihara - Okayama University of Science (Japan)
Masahiro Kuroda - Okayama University of Science (Japan)
Yuichi Mori - Okayama University of Science (Japan) [presenting]
Masaya Iizuka - Okayama University (Japan)
Abstract: Nonnegative matrix factorization (NMF) is applied to several problems in data analysis, for example, clustering, pattern recognition and multimedia data analysis. The alternating least squares (ALS) algorithm is a simple iterative method to give us a factorization in the sense of Frobenius norm of matrices. When applying the ALS algorithm to NMF of large scale data matrix, the algorithm converges slowly because its convergence is almost linear. We propose two component-wise acceleration methods of the ALS algorithm for improving its rate of convergence. These acceleration methods are based on a two point acceleration scheme called Aitken delta-squared method and a three point acceleration scheme by the use of a rational interpolation. The three point acceleration scheme has a better convergence property than the two point acceleration scheme. We prove the fast convergence property of the proposed accelerations under the convergence condition of the ALS algorithm, and evaluate the effectiveness of the proposed accelerations for NMF in numerical experiments.