Stephen Vavasis
University of Waterloo
14 mars 2008 de 16 h 00 à 18 h 00 (heure de Montréal/HNE) Sur place
Colloque par Stephen Vavasis (University of Waterloo)
Nonnegative Matrix Factorization (NMF) has emerged in the past decade as an important tool for information retrieval and clustering. NMF was originally considered as early as 1983 in the mathematical literature, but it did not become popular for information retrieval until work by Lee and Seung in 1999. It has been successfully applied to text and image databases, biochemical laboratory data, and even music. The most popular class of algorithms uses local improvement heuristics, but another class of algorithms based on greedy rank-one downdating has also shown promise. We describe our development of a greedy downdating algorithm motivated in part by the singular value decomposition. We prove that it can successfully classify text databases in a model of text and find features in images in an image model. The new algorithm performs well in practice on standard databases. We also consider the complexity of the NMF problem, showing that it is NP-hard and relating it to a problem in polyhedral combinatorics. Parts of this talk are joint with with M. Biggs and A. Ghodsi of Waterloo.
Adresse
UQAM, Pav. Sherbrooke, 200, rue Sherbrooke O., salle SH-3420