Hardness of some optimization problems over correlation polyhedra
Establishes computational hardness for fundamental problems in optimization over correlation polyhedra, affecting researchers in combinatorial optimization and signal processing.
The paper proves NP-hardness of membership, rank, and relaxed rank problems for the correlation polytope and its cone, which are relevant to signal processing and statistics.
We prove the \textbf{NP}-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the $n\times 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 $\ell_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.