Open Research Index

The Continuous Relaxation of Sparse PCA is NP-hard

Linbin Li, Yong Xia

arXivarxiv/2607.09429Jul 10, 2026math.OCscore 0

Maximizing a symmetric quadratic form under simultaneous L1 norm inequality and L2 norm equality constraints is a standard and widely used continuous relaxation for Sparse Principal Component Analysis (SPCA). This paper settles the computational complexity of this continuous formulation by proving it is NP-hard. Furthermore, the variant with both L1 and L2 norm inequalities is also shown to be NP-hard.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.09429
curl -X POST /api/v1/records/arxiv/2607.09429/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09429/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'