Rational and real positive semidefinite rank can be different

详细信息查看全文

作者：Hamza Fawzi^a ; ^{hfawzi@mit.edu" class="auth_mail" title="E-mail the corresponding author} ; Joã ; o Gouveia^b ; Richard Z. Robinson^c
关键词：Matrix factorization ; Positive semidefinite rank ; Semidefinite programming
刊名：Operations Research Letters
出版年：2016
出版时间：January 2016
年：2016
卷：44
期：1
页码：59-60
全文大小：391 K

文摘

Given a p×q

low="scroll"> p \times q

nonnegative matrix M

low="scroll"> M

, the psd rank of M

low="scroll"> M

is the smallest integer k

low="scroll"> k

such that there exist k×k

low="scroll"> k \times k

real symmetric positive semidefinite matrices A₁,…,A_p

low="scroll"> A_{1}, \dots, A_{p}

and B₁,…,B_q

low="scroll"> B_{1}, \dots, B_{q}

such that M_ij=〈A_i,B_j〉

low="scroll"> M_{i j} = 〈 A_{i}, B_{j} 〉

for i=1,…,p

low="scroll"> i = 1, \dots, p

and j=1,…,q

low="scroll"> j = 1, \dots, q

. When the entries of M

low="scroll"> M

are rational it is natural to consider the rational-restricted psd rank of M

low="scroll"> M

, where the factors A_i

low="scroll"> A_{i}

and B_j

low="scroll"> B_{j}

are required to have rational entries. It is clear that the rational-restricted psd rank is always an upper bound to the usual psd rank. We show that this inequality may be strict by exhibiting a matrix with psd rank four whose rational-restricted psd rank is strictly greater than four.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700