Friday, November 23, 2007
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2007

Steve Vavasis
University of Waterloo

Greedy Algorithms and Complexity for Nonnegative Matrix Factorization

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 did not become popular for information retrieval until the work of 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 a lot of promise. We describe our development of a greedy downdating algorithm and prove that it can successfully classify text databases in some restricted models of text. 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 represent joint work with Michael Biggs (UW) and Ali Ghodsi (UW).