solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看136次
Exploring the bounds on the positive semidefinite rank. (arXiv:1704.06507v1 [cs.CC])
来源于:arXiv
The nonnegative and positive semidefinite (PSD-) ranks are closely connected
to the nonnegative and positive semidefinite extension complexities of a
polytope, which are the minimal dimensions of linear and SDP programs which
represent this polytope. Though some exponential lower bounds on the
nonnegative and PSD- ranks has recently been proved for the slack matrices of
some particular polytopes, there are still no tight bounds for these
quantities. We explore some existing bounds on the PSD-rank and prove that they
cannot give exponential lower bounds on the extension complexity. Our approach
consists in proving that the existing bounds are upper bounded by the
polynomials of the regular rank of the matrix, which is equal to the dimension
of the polytope (up to an additive constant). As one of the implications, we
also retrieve an upper bound on the mutual information of an arbitrary matrix
of a joint distribution, based on its regular rank. 查看全文>>