A universality theorem for nonnegative matrix factorizations

Abstract

Let $A$ be a matrix with nonnegative real entries. A nonnegative factorization of size $k$ is a representation of $A$ as a sum of $k$ nonnegative rank-one matrices. The space of all such factorizations is a bounded semialgebraic set, and we prove that spaces arising in this way are universal. More presicely, we show that every bounded semialgebraic set $U$ is rationally equivalent to the set of nonnegative size-$k$ factorizations of some matrix $A$ up to a permutation of matrices in the factorization. We prove that, if $U\subset {\mathbb{R}}^n$ is given as the zero locus of a polynomial with coefficients in $\mathbb{Q}$, then such a pair $(A,k)$ can be computed in polynomial time. This result gives a complete description of the algorithmic complexity of nonnegative rank, and it also allows one to solve the problem of Cohen and Rothblum on nonnegative factorizations restricted to matrices over different subfields of $\mathbb{R}$.

8 pages, an introduction is added, the proofs are written more accurately

References in corpus (3)

• Factoring nonnegative matrices with linear programs
• How hard is the tensor rank?
• The Art Gallery Problem is $\exists \mathbb{R}$-complete

Cited by in corpus (7)

• A Universality Theorem for Nested Polytopes
• Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
• Smoothed Analysis of Order Types
• Smoothed Analysis of the Art Gallery Problem
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Geometric Embeddability of Complexes is $\exists \mathbb{R}$-complete
• On tropical and nonnegative factorization ranks of band matrices