A Randomized Rounding Algorithm for Sparse PCA


We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. In the proposed approach, we first solve an l1-penalized version of the NP-hard sparse PCA optimization problem and then we use a randomized rounding strategy to sparsify the resulting dense solution. Our main theoretical result guarantees an additive error approximation and provides a tradeoff between sparsity and accuracy. Extensive experimental evaluation indicates that the proposed approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.

ACM Transactions on Knowledge Discovery from Data, Volume 11 Issue 3, April 2017