Lower bounds on nonnegative rank via nonnegative nuclear norms
The nonnegative rank of an entrywise nonnegative matrix A ∈ R[m×n over +] is the smallest integer r such that A can be written as A = UV where U ∈ R[m×r over +] and V ∈ R[r×n over +] are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communica...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100983 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811088293317574656 |
|---|---|
| author | Fawzi, Hamza Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Fawzi, Hamza Parrilo, Pablo A. |
| author_sort | Fawzi, Hamza |
| collection | MIT |
| description | The nonnegative rank of an entrywise nonnegative matrix A ∈ R[m×n over +] is the smallest integer r such that A can be written as A = UV where U ∈ R[m×r over +] and V ∈ R[r×n over +] are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity. Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications. In this paper we propose a new lower bound on the nonnegative rank which, unlike most existing lower bounds, does not solely rely on the matrix sparsity pattern and applies to nonnegative matrices with arbitrary support. The idea involves computing a certain nuclear norm with nonnegativity constraints which allows to lower bound the nonnegative rank, in the same way the standard nuclear norm gives lower bounds on the standard rank. Our lower bound is expressed as the solution of a copositive programming problem and can be relaxed to obtain polynomial-time computable lower bounds using semidefinite programming. We compare our lower bound with existing ones, and we show examples of matrices where our lower bound performs better than currently known ones. |
| first_indexed | 2024-09-23T13:59:55Z |
| format | Article |
| id | mit-1721.1/100983 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:59:55Z |
| publishDate | 2016 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1009832022-10-01T18:27:22Z Lower bounds on nonnegative rank via nonnegative nuclear norms Fawzi, Hamza Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Fawzi, Hamza Parrilo, Pablo A. The nonnegative rank of an entrywise nonnegative matrix A ∈ R[m×n over +] is the smallest integer r such that A can be written as A = UV where U ∈ R[m×r over +] and V ∈ R[r×n over +] are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity. Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications. In this paper we propose a new lower bound on the nonnegative rank which, unlike most existing lower bounds, does not solely rely on the matrix sparsity pattern and applies to nonnegative matrices with arbitrary support. The idea involves computing a certain nuclear norm with nonnegativity constraints which allows to lower bound the nonnegative rank, in the same way the standard nuclear norm gives lower bounds on the standard rank. Our lower bound is expressed as the solution of a copositive programming problem and can be relaxed to obtain polynomial-time computable lower bounds using semidefinite programming. We compare our lower bound with existing ones, and we show examples of matrices where our lower bound performs better than currently known ones. United States. Air Force Office of Scientific Research (FA9550-11-1-0305) 2016-01-25T18:12:45Z 2016-01-25T18:12:45Z 2014-11 2014-10 Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/100983 Fawzi, Hamza, and Pablo A. Parrilo. “Lower Bounds on Nonnegative Rank via Nonnegative Nuclear Norms.” Math. Program. 153, no. 1 (November 12, 2014): 41–66. https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1007/s10107-014-0837-2 Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Fawzi, Hamza Parrilo, Pablo A. Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title | Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title_full | Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title_fullStr | Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title_full_unstemmed | Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title_short | Lower bounds on nonnegative rank via nonnegative nuclear norms |
| title_sort | lower bounds on nonnegative rank via nonnegative nuclear norms |
| url | http://hdl.handle.net/1721.1/100983 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT fawzihamza lowerboundsonnonnegativerankvianonnegativenuclearnorms AT parrilopabloa lowerboundsonnonnegativerankvianonnegativenuclearnorms |