Nonnegative factorization and the maximum edge biclique problem

Nicolas GILLIS () and François Glineur
Additional contact information
Nicolas GILLIS: Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium

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

Abstract: Nonnegative matrix factorization (NMF) is a data analysis technique based on the approximation of a nonnegative matrix with a product of two nonnegative factors, which allows compression and interpretation of nonnegative data. In this paper, we study the case of rank-one factorization and show that when the matrix to be factored is not required to be nonnegative, the corresponding problem (R1NF) becomes NP-hard. This sheds new light on the complexity of NMF since any algorithm for fixed-rank NMF must be able to solve at least implicitly such rank-one subproblems. Our proof relies on a reduction of the maximum edge biclique problem to R1NF. We also link stationary points of R1NF to feasible solutions of the biclique problem, which allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1NF. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets.

Keywords: nonnegative matrix factorization; rank-one factorization; maximum edge biclique problem; algorithmic complexity; biclique finding algorithm (search for similar items in EconPapers)
Date: 2010-10-01
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link)
http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2010_59web.pdf

Related works:
Working Paper: Nonnegative factorization and the maximum edge biclique problem (2008)
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: http://EconPapers.repec.org/RePEc:cor:louvco:2010059

Access Statistics for this paper

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