|
Friday, November 23, 2007 |
|
|
|
|
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.
|