Exact and heuristic algorithms for semi-nonnegative matrix factorization

DOI10.1137/140993272MaRDI QIDQ3195441zbMATH OpenOpenAlexFDO

Authors Nicolas Gillis, Abhishek Kumar

Publication date 19 October 2015

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.7220

zbMATH Keywords

algorithmsinitializationsemi-nonnegative ranklow-rank matrix approximationsemi-nonnegative matrix factorization

Mathematics Subject Classification ID

Factorization of matrices (15A23) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a matrix $M$ (not necessarily nonnegative) and a factorization rank $r$, semi-nonnegative matrix factorization (semi-NMF) looks for a matrix $U$ with $r$ columns and a nonnegative matrix $V$ with $r$ rows such that $UV$ is the best possible approximation of $M$ according to some metric. In this paper, we study the properties of semi-NMF from which we develop exact and heuristic algorithms. Our contribution is threefold. First, we prove that the error of a semi-NMF of rank $r$ has to be smaller than the best unconstrained approximation of rank $r-1$. This leads us to a new initialization procedure based on the singular value decomposition (SVD) with a guarantee on the quality of the approximation. Second, we propose an exact algorithm (that is, an algorithm that finds an optimal solution), also based on the SVD, for a certain class of matrices (including nonnegative irreducible matrices) from which we derive an initialization for matrices not belonging to that class. Numerical experiments illustrate that this second approach performs extremely well, and allows us to compute optimal semi-NMF decompositions in many situations. Finally, we analyze the computational complexity of semi-NMF proving its NP-hardness, already in the rank-one case (that is, for $r=1$), and we show that semi-NMF is sometimes ill-posed (that is, an optimal solution does not exist).

Recommendations

• Computing a nonnegative matrix factorization -- provably
• Nonnegative matrix factorization
• Heuristics for exact nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• scientific article; zbMATH DE number 7404610

Cites work

• scientific article; zbMATH DE number 429516 (Why is no real title available?)
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 2115098 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A continuous characterization of the maximum-edge biclique problem
• Computational Complexity
• Graph implementations for nonsmooth convex programs
• Learning the parts of objects by non-negative matrix factorization
• On the complexity of nonnegative matrix factorization
• On the geometric interpretation of the nonnegative rank
• Semi-nonnegative rank for real matrices and its connection to the usual rank
• Some NP-complete problems in quadratic and nonlinear programming
• Sparse non-negative tensor factorization using columnwise coordinate descent
• Systems of distinct representatives and linear algebra

Cited in

(11)

• Simplex-Structured Matrix Factorization: Sparsity-Based Identifiability and Provably Correct Algorithms
• On the complexity of nonnegative matrix factorization
• Blind source separation with outliers in transformed domains
• Nonnegative matrix factorization via archetypal analysis
• Heuristics for exact nonnegative matrix factorization
• Conic optimization-based algorithms for nonnegative matrix factorization
• scientific article; zbMATH DE number 6795656 (Why is no real title available?)
• Dual simplex volume maximization for simplex-structured matrix factorization
• Computing a nonnegative matrix factorization -- provably
• A new study on clustering of adaptive asymmetric graph regularized semi-nonnegative matrix factorization under orthogonal subspace with auxiliary variable
• Computing a nonnegative matrix factorization -- provably

Describes a project that uses

Uses Software

• CVX

This page was built for publication: Exact and heuristic algorithms for semi-nonnegative matrix factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3195441)