{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}