Approximation Algorithms for Sparse Principal Component Analysis

06/23/2020
by   Agniva Chowdhury, et al.
0

We present three provably accurate, polynomial time, approximation algorithms for the Sparse Principal Component Analysis (SPCA) problem, without imposing any restrictive assumptions on the input covariance matrix. The first algorithm is based on randomized matrix multiplication; the second algorithm is based on a novel deterministic thresholding scheme; and the third algorithm is based on a semidefinite programming relaxation of SPCA. All algorithms come with provable guarantees and run in low-degree polynomial time. Our empirical evaluations confirm our theoretical findings.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset