Positive semidefinite rank
Let M∈R[superscript p×q] be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A[subscript i],B[subscript j] of size k×k such that M[subscript ij]=trace(A[subscript i]B[subscript j]). The psd rank...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106864 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0001-6026-4102 |
| _version_ | 1826210030339227648 |
|---|---|
| author | Gouveia, João Robinson, Richard Z. Thomas, Rekha R. Parrilo, Pablo A Fawzi, Hamza |
| 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 Gouveia, João Robinson, Richard Z. Thomas, Rekha R. Parrilo, Pablo A Fawzi, Hamza |
| author_sort | Gouveia, João |
| collection | MIT |
| description | Let M∈R[superscript p×q] be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A[subscript i],B[subscript j] of size k×k such that M[subscript ij]=trace(A[subscript i]B[subscript j]). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects. |
| first_indexed | 2024-09-23T14:40:14Z |
| format | Article |
| id | mit-1721.1/106864 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:40:14Z |
| publishDate | 2017 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1068642022-09-29T10:06:19Z Positive semidefinite rank Gouveia, João Robinson, Richard Z. Thomas, Rekha R. Parrilo, Pablo A Fawzi, Hamza 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 Let M∈R[superscript p×q] be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A[subscript i],B[subscript j] of size k×k such that M[subscript ij]=trace(A[subscript i]B[subscript j]). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects. United States. Air Force Office of Scientific Research (AFOSR FA9550-11-1-0305) 2017-02-04T00:01:08Z 2017-02-04T00:01:08Z 2015-07 2015-04 2016-05-23T12:11:12Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/106864 Fawzi, Hamza et al. “Positive Semidefinite Rank.” Mathematical Programming 153.1 (2015): 133–177. https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0001-6026-4102 en http://dx.doi.org/10.1007/s10107-015-0922-1 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 | Gouveia, João Robinson, Richard Z. Thomas, Rekha R. Parrilo, Pablo A Fawzi, Hamza Positive semidefinite rank |
| title | Positive semidefinite rank |
| title_full | Positive semidefinite rank |
| title_fullStr | Positive semidefinite rank |
| title_full_unstemmed | Positive semidefinite rank |
| title_short | Positive semidefinite rank |
| title_sort | positive semidefinite rank |
| url | http://hdl.handle.net/1721.1/106864 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0001-6026-4102 |
| work_keys_str_mv | AT gouveiajoao positivesemidefiniterank AT robinsonrichardz positivesemidefiniterank AT thomasrekhar positivesemidefiniterank AT parrilopabloa positivesemidefiniterank AT fawzihamza positivesemidefiniterank |