Tutte seminar - Nicolas Gillis

Fast and Robust Algorithms for Separable Nonnegative Matrix Factorization

Abstract:

Nonnegative Matrix Factorization (NMF) is a linear dimensionality reduction technique for nonnegative data. It consists in approximating a nonnegative data matrix with the product of two low-rank nonnegative matrices. NMF has become a very popular technique in data mining and machine learning because it automatically extracts meaningful features through a sparse and part-based representation. Although NMF is NP-hard in general, it has been shown very recently that it is possible to compute an optimal solution under the assumption that the input nonnegative data matrix is separable (i.e., there exists a cone spanned by a small subset of the columns containing all columns). Current approaches solving the separable NMF problem are either computationally expensive or not robust to noise. In this talk, we first introduce NMF and illustrate its usefulness with some application examples (namely, image processing, text mining and hyperspectral data analysis). Then, we present a new family of fast and robust recursive algorithms for separable NMF problems.

This is joint work with Stephen Vavasis.