Randomized Algorithms for Sparse PCA and Determinant Estimation

Date
9/1/2017
Location
11:30AM at LWSN B134
Speaker
Prof. Petros Drineas, Purdue University
Title
Randomized Algorithms for Sparse PCA and Determinant Estimation
Host
Description

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. Time permitting, we will also discuss a simple randomized algorithm to estimate the log determinant of a symmetric positive definite matrix.