Nonnegative matrix factorization requires irrationality

DOI10.1137/16M1078835zbMATH Open1369.15020arXiv1605.06848OpenAlexW2963241018MaRDI QIDQ5283249FDOQ5283249

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• 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
• The role of rationality in integer-programming relaxations

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)