Greedy Algorithms and Complexity for Nonnegative Matrix Factorization
| Speaker: | Steve Vavasis |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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 (UWaterloo) and Ali Ghodsi (UWaterloo).