Nonnegative matrix factorization requires irrationality

DOI10.1137/16M1078835MaRDI QIDQ5283249zbMATH OpenOpenAlexFDO

Authors Stefan Kiefer, Ines Marušić, Mahsa Shirmohammadi, Dmitry Chistikov, James Worrell

Publication date 21 July 2017

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

nonnegative matrix factorizationnonnegative rank

Mathematics Subject Classification ID

Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Abstract: Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $nimesm$ matrix $M$ into a product of a nonnegative $nimesd$ matrix $W$ and a nonnegative $dimesm$ matrix $H$. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix $M$ always has an NMF of minimal inner dimension $d$ whose factors $W$ and $H$ are also rational. We answer this question negatively, by exhibiting a matrix for which $W$ and $H$ require irrational entries.

Recommendations

• On rationality of nonnegative matrix factorization
• On restricted nonnegative matrix factorization
• On the complexity of nonnegative matrix factorization
• The NMF problem and lattice-subspaces
• Nonnegative matrix factorization and I-divergence alternating minimization

Cites work

• scientific article; zbMATH DE number 4008576 (Why is no real title available?)
• Algebraic boundary of matrices of nonnegative rank at most three
• An almost optimal algorithm for computing nonnegative rank
• Computing a nonnegative matrix factorization -- provably
• Expressing combinatorial optimization problems by linear programs
• Finding minimal convex nested polygons
• Fixed points of the EM algorithm and nonnegative rank boundaries
• Nonnegative matrix factorization requires irrationality
• Nonnegative rank depends on the field
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On rationality of nonnegative matrix factorization
• On restricted nonnegative matrix factorization
• On the complexity of approximating and illuminating three-dimensional convex polyhedra
• On the complexity of nonnegative matrix factorization
• On the geometric interpretation of the nonnegative rank
• Perturbation of matrices and nonnegative rank with a view toward statistical models
• Regularization, optimization, kernels, and support vector machines
• Sparse and unique nonnegative matrix factorization through data preprocessing
• Stochastic factorizations, sandwiched simplices and the topology of the space of explanations

Cited in

(9)

• The role of rationality in integer-programming relaxations
• Nonnegative matrix factorization requires irrationality
• On the complexity of nonnegative matrix factorization
• On rationality of nonnegative matrix factorization
• On restricted nonnegative matrix factorization
• The nonnegative rank of a matrix: hard problems, easy solutions
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Nonnegative rank depends on the field
• Extension complexity of polytopes with few vertices or facets

This page was built for publication: Nonnegative matrix factorization requires irrationality

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