Approximation Algorithms for Sparse Principal Component Analysis

Understand

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 algorithm for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix.
• Our first thresholding algorithm using the Singular Value Decomposition is conceptually simple; is faster than current state-of-the-art; and performs well in practice.