An almost optimal algorithm for computing nonnegative rank

DOI10.1137/1.9781611973105.104MaRDI QIDQ5741813zbMATH OpenOpenAlexFDO

Authors Ankur Moitra

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $mimesn$ is at most $r$ which runs in time $(nm{)}^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on methods for finding a solution to a system of polynomial inequalities (if one exists). Notably, the best algorithms for this task run in time exponential in the number of variables but polynomial in all of the other parameters (the number of inequalities and the maximum degree). Hence these algorithms motivate natural algebraic questions whose solution have immediate {em algorithmic} implications: How many variables do we need to represent the decision problem, does $M$ have nonnegative rank at most $r$? A naive formulation uses $nr+mr$ variables and yields an algorithm that is exponential in $n$ and $m$ even for constant $r$. (Arora, Ge, Kannan, Moitra, STOC 2012) recently reduced the number of variables to $2r^2{2}^r$, and here we exponentially reduce the number of variables to $2r^2$ and this yields our main algorithm. In fact, the algorithm that we obtain is nearly-optimal (under the Exponential Time Hypothesis) since an algorithm that runs in time $(nm{)}^{o(r)}$ would yield a subexponential algorithm for 3-SAT . Our main result is based on establishing a normal form for nonnegative matrix factorization - which in turn allows us to exploit algebraic dependence among a large collection of linear transformations with variable entries. Additionally, we also demonstrate that nonnegative rank cannot be certified by even a very large submatrix of $M$, and this property also follows from the intuition gained from viewing nonnegative rank through the lens of systems of polynomial inequalities.

Recommendations

• An almost optimal algorithm for computing nonnegative rank
• The nonnegative rank of a matrix: hard problems, easy solutions
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Computing a nonnegative matrix factorization -- provably
• Computing a nonnegative matrix factorization -- provably

Cited in

(17)

• Fixed-parameter algorithms for Kemeny rankings
• On the geometric interpretation of the nonnegative rank
• Nonnegative rank depends on the field
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Computing a nonnegative matrix factorization -- provably
• Heuristics for exact nonnegative matrix factorization
• Algebraic boundary of matrices of nonnegative rank at most three
• Common information and unique disjointness
• A polynomial-time algorithm for computing low CP-rank decompositions
• On the nonnegative rank of distance matrices
• The nonnegative rank of a matrix: hard problems, easy solutions
• Rank reversal and Rank Preservation in ANP method
• An almost optimal algorithm for computing nonnegative rank
• Conic optimization-based algorithms for nonnegative matrix factorization
• Hard submatrices for nonnegative rank and communication complexity
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Positive semidefinite rank

This page was built for publication: An almost optimal algorithm for computing nonnegative rank

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