On restricted nonnegative matrix factorization

DOI10.4230/LIPICS.ICALP.2016.103MaRDI QIDQ4598244zbMATH OpenOpenAlexFDO

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

Publication date 19 December 2017

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

zbMATH Keywords

labelled Markov chainsminimizationnonnegative matrix factorizationnonnegative rankprobabilistic automata

Mathematics Subject Classification ID

Factorization of matrices (15A23) Formal languages and automata (68Q45)

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$. Restricted NMF requires in addition that the column spaces of $M$ and $W$ coincide. Finding the minimal inner dimension $d$ is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974. Furthermore, we investigate whether a rational matrix $M$ always has a restricted NMF of minimal inner dimension whose factors $W$ and $H$ are also rational. We show that this holds for matrices $M$ of rank at most $3$ and we exhibit a rank-$4$ matrix for which $W$ and $H$ require irrational entries.

Recommendations

• On rationality of nonnegative matrix factorization
• Nonnegative matrix factorization requires irrationality
• On the complexity of nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• Computing a nonnegative matrix factorization -- provably

Cited in

(12)

• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• Non-negative matrix factorization under equality constraints -- a study of industrial source identification
• scientific article; zbMATH DE number 5631077 (Why is no real title available?)
• On rationality of nonnegative matrix factorization
• Nonnegative matrix factorization requires irrationality
• On the complexity of recognizing nerves of convex sets
• The complexity of recognizing geometric hypergraphs
• On classifying continuous constraint satisfaction problems
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Recognition of unit segment and polyline graphs is \(\exists \mathbb{R} \)-complete
• The complexity of recognizing geometric hypergraphs
• On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices

This page was built for publication: On restricted nonnegative matrix factorization

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