Algorithms for Near-Separable Nonnegative Matrix Factorization

March 27, 2013
Abhishek Kumar | University of Maryland, College Park

The goal in nonnegative matrix factorization (NMF) is to express, exactly or approximately, a given matrix as a product of two nonnegative matrices of smaller inner dimension. NMFs arise naturally in a variety of signal separation and unsupervised feature extraction problems, such as modeling topics in text and analyzing Hyperspectral images. Computing NMF has been shown to be NP-hard (Vavasis, 2009). Popular methods for solving the NMF problem use local search to reach a locally optimal solution. Very recently, a new class of algorithms have been proposed to solve NMF exactly under certain separability assumptions on the generative model. In this talk, I will first survey these recent developments, evaluate their potential for topic modeling applications, and then present new algorithms that solve the factorization problem exactly under the same assumptions, but are superior in terms of scalability and noise-robustness. I will also briefly talk about extensions to other factorization losses like ℓ₁-loss and Bregman divergences, and show applications to foreground-background separation in Video. This talk is based on joint work with Vikas Sindhwani and Prabhanjan Kambadur.

Speaker Details

Abhishek Kumar is a Ph.D. student in Computer Science at the University of Maryland, College Park. His research interests broadly lie in the area of machine learning. More specifically, he has worked on learning with multiple kernels and similarities, transfer and multitask learning, and nonnegative matrix factorization. He spent the summer of 2011 in the Machine Learning group at NEC Laboratories America, and summer of 2012 in the Business Analytics and Mathematical Sciences dept. at IBM T.J. Watson Research Center. Before joining the Ph.D. program, he completed his Masters in Electrical Engineering from University of Texas at Dallas where he worked on environment mismatch compensation methods for robust speech recognition.