Sparse PCA on fixed-rank matrices

DOI10.1007/S10107-022-01769-9MaRDI QIDQ6387711arXivFDO

Authors Alberto Del Pia

Publication date 7 January 2022

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10107-022-01769-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

arXiv classification

cs.DMcs.LGmath.OC

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.

This page was built for publication: Sparse PCA on fixed-rank matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6387711)