A randomized algorithm based on the basic SDP relaxation for sparse PCA achieves an approximation ratio bounded by the sparsity constant with high probability and O(log d) on average under a technical assumption satisfied for low-rank or exponentially decaying eigenvalue SDP solutions.
Sparse principal component analysis and its $l_1$-relaxation
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component analysis (SPCA). One popular approach to achieve sparsity is to replace the l0 constraint by an l1 constraint. In this paper, we prove that, independent of the data, the optimal objective function value of the problem with l0 constraint is within a constant factor of the the optimal objective function value of the problem with l1 constraint. To the best of our knowledge, this is the first formal relationship established between the l0 and the l1 constraint version of the problem.
fields
stat.ML 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
A randomized algorithm based on the basic SDP relaxation for sparse PCA achieves an approximation ratio bounded by the sparsity constant with high probability and O(log d) on average under a technical assumption satisfied for low-rank or exponentially decaying eigenvalue SDP solutions.