cs.LGNov 11, 2026

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

Authors: Alberto Del Pia, Dekun Zhou

Organizations: Department of Industrial and Systems Engineering & Wisconsin Institute for Discovery, University of Wisconsin–Madison, Madison, WI, USA.

Abstract

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×rn\times r matrix RR and dd sparsity constants si≤ns_i \le n, and the goal is to find an n×dn\times d matrix XX with orthonormal columns that maximizes ∥R⊤X∥F2\|R^\top X\|_F^2, such that column ii has at most sis_i non-zero entries. Here RR⊤RR^\top plays the role of the covariance matrix and has rank at most rr. We show that SPCA is NP-hard even when r=d=2r = d = 2, but admits a fully polynomial-time approximation scheme (FPTAS) when rr and dd are fixed. The returned solution has exactly orthonormal columns, and its entries are real algebraic numbers in an exact representation. For fixed εε, the number of steps of the algorithm is linear in nn up to a polylogarithmic factor. Our approach reduces SPCA to a sparse version of the orthogonal Procrustes problem, that is, to maximizing a linear function over the feasible region of SPCA. We show that this problem is NP-hard even for d=2d = 2, and we give an FPTAS for it when dd is fixed. This FPTAS combines approximate dynamic programming over the rows, two-column updates that restore exact orthogonality, and an exact computation of the few variables for which these updates are not available.

Figures & tables

Explore similar work

CardsList
  1. A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA

    Mar 1, 2026Difei Cheng, Qiao HuPrincipal Component Analysis

  2. Combinatorial Sparse PCA Beyond the Spiked Identity Model

    Mar 3, 2026Syamantak Kumar, Purnamrita Sarkar, Kevin Tian +1Principal Component Analysis

  3. msPCA: An R Package for Sparse PCA with Multiple Components

    Jul 6, 2026Ryan Cory-Wright, Jean PauphiletPrincipal Component AnalysisDimensionality Reduction