Before revision:  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 .
After revision:  and the third algorithm is based on a semidefinite programming relaxation and then uses a novel, two step, deterministic thresholding scheme to compute a sparse principal vector. It works very well in practice and, remarkably, this solid practical performance is accurately predicted by our theoretical bounds, which bridge the theory-practice gap better than current state-of-the-art .