Id: arxiv/2611.15810 Url: https://arxiv.org/abs/2611.15810 Tags: cs.LG, math.OC Score: 0 Title: Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS Domain: cs.LG Source: arxiv Authors: Alberto Del Pia, Dekun Zhou Reviews: 0 Subject: cs.LG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-11 Page: https://delphi.science/r/arxiv/2611.15810 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…