Seminar Details
2009-03-03 (14.00) : New variants of nonnegative matrix factorization for sparsity improvement and maximum biclique finding
At Euler building
Organized by Mathematical Engineering
Speaker :
Gillis, Nicolas (UMons (Belgium))
Abstract :
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 in the
factorization of a nonnegative matrix by 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 solve 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 to a graph partitioning problem, namely the maximum-edge biclique problem (MBP).
This reduction allows us design a new type of simple and efficient algorithm for MBP.