An Almost Optimal Algorithm for Computing Nonnegative Rank
Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension m \times n$ is at most r which runs in time (nm)[superscript 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 f...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| Online Access: | http://hdl.handle.net/1721.1/108665 https://orcid.org/0000-0001-7047-0495 |
| _version_ | 1826199139630710784 |
|---|---|
| author | Moitra, Ankur |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Moitra, Ankur |
| author_sort | Moitra, Ankur |
| collection | MIT |
| description | Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension m \times n$ is at most r which runs in time (nm)[superscript 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 algebraic questions whose solution have immediate algorithmic implications: How many variables do we need to represent the decision problem, and 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 et al. [Proceedings of STOC, 2012, pp. 145--162] recently reduced the number of variables to 2r[superscript 2] 2[superscript r], and here we exponentially reduce the number of variables to 2r[superscript 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)[superscript o(r)] would yield a subexponential algorithm for 3-SAT [Proceedings of STOC, 2012, pp. 145--162]. 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. |
| first_indexed | 2024-09-23T11:15:20Z |
| format | Article |
| id | mit-1721.1/108665 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:15:20Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1086652022-10-01T02:24:03Z An Almost Optimal Algorithm for Computing Nonnegative Rank Moitra, Ankur Massachusetts Institute of Technology. Department of Mathematics Moitra, Ankur Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension m \times n$ is at most r which runs in time (nm)[superscript 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 algebraic questions whose solution have immediate algorithmic implications: How many variables do we need to represent the decision problem, and 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 et al. [Proceedings of STOC, 2012, pp. 145--162] recently reduced the number of variables to 2r[superscript 2] 2[superscript r], and here we exponentially reduce the number of variables to 2r[superscript 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)[superscript o(r)] would yield a subexponential algorithm for 3-SAT [Proceedings of STOC, 2012, pp. 145--162]. 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. National Science Foundation (U.S.) (Computing and Innovation Fellowship) National Science Foundation (U.S.) (grant DMS-0835373) 2017-05-04T17:00:24Z 2017-05-04T17:00:24Z 2016-02 2014-10 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/108665 Moitra, Ankur. “An Almost Optimal Algorithm for Computing Nonnegative Rank.” SIAM Journal on Computing 45.1 (2016): 156–173. c 2016 Society for Industrial and Applied Mathematics https://orcid.org/0000-0001-7047-0495 en_US http://dx.doi.org/10.1137/140990139 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics |
| spellingShingle | Moitra, Ankur An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title | An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title_full | An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title_fullStr | An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title_full_unstemmed | An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title_short | An Almost Optimal Algorithm for Computing Nonnegative Rank |
| title_sort | almost optimal algorithm for computing nonnegative rank |
| url | http://hdl.handle.net/1721.1/108665 https://orcid.org/0000-0001-7047-0495 |
| work_keys_str_mv | AT moitraankur analmostoptimalalgorithmforcomputingnonnegativerank AT moitraankur almostoptimalalgorithmforcomputingnonnegativerank |