Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS
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 matrix and sparsity constants , and the goal is to find an matrix with orthonormal columns that maximizes , such that column has at most non-zero entries. Here plays the role of the covariance matrix and has rank at most . We show that SPCA is NP-hard even when , but admits a fully polynomial-time approximation scheme (FPTAS) when and 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 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 , and we give an FPTAS for it when 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
| Parameter | Value | Role |
|---|---|---|
| error allowed for at the root | ||
| upper bound on the number of hard variables | ||
| upper bound on the side length of the boxes | ||
| number of intervals covering | ||
| inverse of relative mesh size in | ||
| determines the smallest non-zero magnitude in |
Principal Component Analysis
Principal component analysis (PCA) finds orthogonal directions of greatest variance for data compression, visualization, denoising, and feature discovery.
See all 72 papers