Positive semidefinite rank

• 成果类型: Article
• 署名作者: Fawzi, Hamza; Gouveia, Joao; Parrilo, Pablo A.; Robinson, Richard Z.; Thomas, Rekha R.
• 署名单位: Massachusetts Institute of Technology (MIT); Universidade de Coimbra; University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0922-1
• 发表日期: 2015
• 页码: 133-177
• 关键词: nonnegative rank; complexity; matrices; factorizations; optimization; PROGRAMS; bounds; cone; sets

摘要

Let M is an element of R-pxq be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices of size such that . 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.