NP-Hardness and Inapproximability of Sparse PCA

The earliest reference to principal components analysis (PCA) is in [14]. Since then, PCA has evolved into a classic tool for data analysis. A challenge for the interpretation of the principal components (or factors) is that they can be linear combinations of all the original variables. When the original variables have direct physical significance (e.g.