A Randomized Rounding Algorithm for Sparse PCA
This work addresses the sparse PCA problem for data analysis and dimensionality reduction, but it is incremental as it builds on existing methods with a new rounding strategy.
The paper tackles the NP-hard sparse PCA problem by proposing a two-step algorithm that first solves an L1-penalized version and then applies randomized rounding to sparsify the solution, achieving competitive performance compared to state-of-the-art toolboxes like Spasm.
We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. Our approach first solves a L1 penalized version of the NP-hard sparse PCA optimization problem and then uses 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. Our experimental evaluation indicates that our approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.