期刊名称:CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度:2009
卷号:1
出版社:Center for Operations Research and Econometrics (UCL), Louvain
摘要: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.