Delphi.science

Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS

Source: arxiv.org/abs/2611.15810

Alberto Del Pia, Dekun Zhou

arXivarxiv/2611.15810Nov 11, 2026cs.LGscore 0

In sparse principal component analysis (SPCA) with several components, each must be sparse and all must be pairwise orthogonal. When the supports of the components overlap, these two requirements interact. For a covariance matrix of fixed rank, polynomial-time algorithms with optimality or approximation guarantees are known for one component, and for several components with disjoint supports or with a common support. We study the general model, with individual sparsity constants and arbitrary support overlaps. We are given a rational $n\times r$ matrix $R$ and $d$ sparsity constants $s_i \le…

JSONText

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