Hardness of some optimization problems over correlation polyhedra
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.02896
curl -X POST /api/v1/records/arxiv/2605.02896/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.02896/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'