Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we stud...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103632 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811070586597670912 |
|---|---|
| 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 a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of “positive” ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks. Additionally the bounds we propose can be computed by semidefinite programming using sum-of-squares relaxations. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that enjoys other interesting structural properties. For the case of the nonnegative rank we show that our bound has an appealing connection with existing combinatorial bounds and other norm-based bounds. For example we show that our lower bound is a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lovász [bar over ϑ] number of the rectangle graph of the matrix. We also prove that the lower bound is always greater than or equal to the hyperplane separation bound (and other similar “norm-based” bounds). We also discuss the case of the tensor nonnegative rank as well as the cp-rank, and compare our bound with existing results. |
| first_indexed | 2024-09-23T08:38:24Z |
| format | Article |
| id | mit-1721.1/103632 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:38:24Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1036322022-09-23T13:31:02Z Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank 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 Parrilo, Pablo A. Fawzi, Hamza The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of “positive” ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks. Additionally the bounds we propose can be computed by semidefinite programming using sum-of-squares relaxations. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that enjoys other interesting structural properties. For the case of the nonnegative rank we show that our bound has an appealing connection with existing combinatorial bounds and other norm-based bounds. For example we show that our lower bound is a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lovász [bar over ϑ] number of the rectangle graph of the matrix. We also prove that the lower bound is always greater than or equal to the hyperplane separation bound (and other similar “norm-based” bounds). We also discuss the case of the tensor nonnegative rank as well as the cp-rank, and compare our bound with existing results. 2016-07-15T21:47:49Z 2016-07-15T21:47:49Z 2015-08 2016-06-30T12:07:25Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/103632 Fawzi, Hamza, and Pablo A. Parrilo. “Self-Scaled Bounds for Atomic Cone Ranks: Applications to Nonnegative Rank and Cp-Rank.” Mathematical Programming 158.1–2 (2016): 417–465. https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 en http://dx.doi.org/10.1007/s10107-015-0937-7 Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Fawzi, Hamza Parrilo, Pablo A. Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title | Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title_full | Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title_fullStr | Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title_full_unstemmed | Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title_short | Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank |
| title_sort | self scaled bounds for atomic cone ranks applications to nonnegative rank and cp rank |
| url | http://hdl.handle.net/1721.1/103632 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT fawzihamza selfscaledboundsforatomicconeranksapplicationstononnegativerankandcprank AT parrilopabloa selfscaledboundsforatomicconeranksapplicationstononnegativerankandcprank |