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 s