Sparse PCA on fixed-rank matrices
From MaRDI portal
Publication:6387711
DOI10.1007/S10107-022-01769-9zbMath1512.90157arXiv2201.02487MaRDI QIDQ6387711
Publication date: 7 January 2022
Abstract: Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)
This page was built for publication: Sparse PCA on fixed-rank matrices
