Nonnegative Matrix Factorization: Fast Active-set type Algorithms and Comparisons

Applied and Computational Mathematics Seminar
Monday, February 22, 2010 - 13:00
1 hour (actually 50 minutes)
Skiles 255
CSE, Georgia Institute of Technology
Nonnegative Matrix Factorization (NMF) has attracted much attention during the past decade as a dimension reduction method in machine learning and data analysis. NMF provides a lower rank approximation of a nonnegative high dimensional matrix by factors whose elements are also nonnegative. Numerous success stories were reported in application areas including text clustering, computer vision, and cancer class discovery.   In this talk, we present novel algorithms for NMF and NTF (nonnegative tensor factorization) based on the alternating non-negativity constrained least squares (ANLS) framework. Our new algorithm for NMF is built upon the block principal pivoting method for the non-negativity constrained least squares problem that overcomes some limitations of the classical active set method. The proposed NMF algorithm can naturally be extended to obtain highly efficient NTF algorithm for PARAFAC (PARAllel FACtor) model. Our algorithms inherit the convergence theory of the ANLS framework and can easily be extended to other NMF formulations such as sparse NMF and NTF with L1 norm constraints. Comparisons of algorithms using various data sets show that the proposed new algorithms outperform existing ones in computational speed as well as the solution quality.   This is a joint work with Jingu Kim and Krishnakumar Balabusramanian.