Nicolas Gillis
F.R.S.-FNRS Research Fellow
Université catholique de Louvain (UCL)
Department of Mathematical Engineering (INMA)
and Center for Operations Research and Econometrics (CORE)
Friday, November 13, 2009 3:00 p.m.,
Manchester Hall, Room 241
New Variants of Nonnegative Matrix Factorization
for Sparsity Improvement and Maximum Biclique Finding
Nonnegative Matrix Factorization (NMF) is a data analysis technique which allows compression and interpretation of nonnegative data. It has been extensively and successfully applied in numerous applications: e.g., text mining, spectral data analysis, blind source separation, image processing, computational biology, graph clustering, recommendation systems, statistical models, etc. NMF consists of the factorization of a nonnegative matrix into the product of two low-rank nonnegative matrices. Because of the nonnegativity constraints, NMF is particularly well-suited to achieve decomposition into parts. In this talk, we first illustrate the usefulness of NMF with some application examples. We then present and analyze several algorithms to produce NMF. In this study, we introduce two new variants of
NMF: Nonnegative Factorization (NF) and Nonnegative Matrix Underapproximation (NMU). NF is a generalization of NMF while NMU enables a recursive procedure for NMF and is particularly well-suited to achieve a better (sparser) part-based decomposition. Algorithms and applications for both NF and NMU are presented. Finally, NF and NMU are shown to be NP-hard using a reduction of a graph partitioning problem: namely, the maximum-edge biclique problem (MBP). This reduction allows us to design a new type of simple and efficient algorithm for MBP.
Refreshments at 2:30 p.m. in Manchester Hall, Room 336