期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension mn is at most r which runs in time (nm)O(r2). 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 {\em 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 2r22r, and here we {\em exponentially} reduce the number of variables to 2r2 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
