Mathematics – Optimization and Control
Scientific paper
2009-02-06
Mathematics
Optimization and Control
Version 2 removed the section about convex reformulations, which was not central to the development of our main results; added
Scientific paper
Nonnegative Matrix Factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc. We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs. We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard Sparse Nonnegative Matrix Factorization techniques.
Gillis Nicolas
Glineur François
No associations
LandOfFree
Using Underapproximations for Sparse Nonnegative Matrix Factorization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Using Underapproximations for Sparse Nonnegative Matrix Factorization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using Underapproximations for Sparse Nonnegative Matrix Factorization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-251661