Some upper and lower bounds on PSD-rank
成果类型：
Article
署名作者：
Lee, Troy; Wei, Zhaohui; de Wolf, Ronald
署名单位：
Nanyang Technological University; National University of Singapore; Centrum Wiskunde & Informatica (CWI); University of Amsterdam
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-016-1052-0
发表日期：
2017
页码：
495-521
关键词：
摘要：
Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.