Using underapproximations for sparse nonnegative matrix factorization

Nicolas Gillis and François Glineur
Additional contact information
Nicolas Gillis: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2009006, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: nonnegative matrix factorization; underapproximation; maximum edge biclique problem; sparsity; image processing (search for similar items in EconPapers)
Date: 2009-02-01
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2009.html (application/pdf)

Related works:
Working Paper: Using underapproximations for sparse nonnegative matrix factorization (2010)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2009006

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().