Using underapproximations for sparse nonnegative matrix factorization
(2009) , 23 pages
Files
coredp2009_6.pdf
Open Access - Adobe PDF
- 918.81 KB
Details
- Authors
- Abstract
- Nonnegative Matrix Factorization (NMF) has gathered a lot of attention in the last decade and has been successfully applied in numerous applications. It consists in the factorization of a nonnegative matrix by the product of two low-rank nonnegative matrices:. MªVW. In this paper, we attempt to solve NMF problems in a recursive way. In order to do that, we introduce a new variant called Nonnegative Matrix Underapproximation (NMU) by adding the upper bound constraint VW£M. Besides enabling a recursive procedure for NMF, these inequalities make NMU particularly well suited to achieve a sparse representation, improving the part-based decomposition. Although NMU is NP-hard (which we prove using its equivalence with the maximum edge biclique problem in bipartite graphs), we present two approaches to solve it: a method based on convex reformulations and a method based on Lagrangian relaxation. Finally, we provide some encouraging numerical results for image processing applications.
- Affiliations
Citations
Gillis, N., & Glineur, F. (2009). Using underapproximations for sparse nonnegative matrix factorization (Core Discussion Papers 2009/6). https://hdl.handle.net/2078.5/249751