Before revision: We present three provably accurate, polynomial time, approximation algorithms for the Sparse Principal Component Analysis (SPCA ) problem, without imposing any restrictive assumptions on the input covariance matrix.
After revision: Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present thresholding as a provably accurate, polynomial time, approximation algorithms for the Sparse Principal Component Analysis (SPCA ) problem, without imposing any restrictive assumptions on the input covariance matrix.