Before revision:  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.
After revision:  The first algorithm is faster than current state-of-the-art; and performs well in practice. On the negative side, our (novel) theoretical bounds do not accurately predict the strong practical performance of this approach. The second algorithm solves a well-known semidefinite programming relaxation of SPCA.