Hardness of some optimization problems over correlation polyhedra

<div> We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n × n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a "relaxed rank" obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. While membership and rank are natural problems for any matrix cone, the relaxed rank problem occurs in some signal processing and statistical applications. </div>