psd rank

Worst-Case Results For Positive Semidefinite Rank

  • João Gouveia
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic n-dimensional polytope with v vertices is at least (nv)^(1/4) improving on previous lower bounds. For polygons with v vertices, we show that psd rank … Read more