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

Mar 1, 2026

A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA

Sparse Principal Component Analysis (SPCA) is an important technique for high-dimensional data analysis, improving interpretability by imposing sparsity on principal components. However, existing methods often fail to simultaneously guarantee sparsity, orthogonality, and optimality of the principal components. To address this challenge, this work introduces a novel Sparse Principal Component Analysis (SPCA) algorithm called GS-SPCA (SPCA with Gram-Schmidt Orthogonalization), which simultaneously enforces sparsity, orthogonality, and optimality. However, the original GS-SPCA algorithm is computationally expensive due to the inherent ℓ0\ell_0-norm constraint. To address this issue, we propose two acceleration strategies: First, we combine Branch-and-Bound with the GS-SPCA algorithm. By incorporating this strategy, we are able to obtain ε\varepsilon-optimal solutions with a trade-off between precision and efficiency, significantly improving computational speed. Second, we propose a decomposition framework for efficiently solving multiple principal components. This framework approximates the covariance matrix using a block-diagonal matrix through a thresholding method, reducing the original SPCA problem to a set of block-wise subproblems on approximately block-diagonal matrices.
Mar 3, 2026

Combinatorial Sparse PCA Beyond the Spiked Identity Model

Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance ΣΣ, whose top eigenvector v∈Rdv \in R^d is ss-sparse. Existing sparse PCA algorithms can be broadly categorized into (1) combinatorial algorithms (e.g., diagonal or elementwise covariance thresholding) and (2) SDP-based algorithms. While combinatorial algorithms are much simpler, they are typically only analyzed under the spiked identity model (where Σ=Id+γvv⊤Σ= I_d + γvv^\top for some γ>0γ> 0), whereas SDP-based algorithms require no additional assumptions on ΣΣ. We demonstrate explicit counterexample covariances ΣΣ against the success of standard combinatorial algorithms for sparse PCA, when moving beyond the spiked identity model. In light of this discrepancy, we give the first combinatorial method for sparse PCA that provably succeeds for general ΣΣ using s2⋅polylog(d)s^2 \cdot \mathrm{polylog}(d) samples and d2⋅poly(s,log⁡(d))d^2 \cdot \mathrm{poly}(s, \log(d)) time, by providing a global convergence guarantee on a variant of the truncated power method of Yuan and Zhang (2013). We provide a natural generalization of our method to recovering a vector in a sparse leading eigenspace. Finally, we evaluate our method on synthetic and real-world sparse PCA datasets.
Jul 6, 2026

msPCA: An R Package for Sparse PCA with Multiple Components

We present msPCA: an open-source R package for sparse principal component analysis with multiple components. It implements an alternating maximization algorithm to generate a set of sparse loading vectors that collectively explain a large fraction of the variance in a dataset, while remaining non-redundant. The algorithm supports two definitions of non-redundancy: either orthogonality of the loading vectors or zero pairwise correlation between principal components (PCs). In the reported benchmarks, msPCA solves sparse PCA problems with thousands of features, achieving competitive runtimes while producing sparse components with controlled feasibility violations and a high fraction of variance explained.