Before revision:  Finally{\em   , we provide improved approximation results for the maximum variance embedding problem for general graphs, by replacing the optimal orthogonal projection (PCA) with a randomized projection approach .
After revision:  Finally{\em , we provide fast combinatorial algorithms that avoid solving a semidefinite relaxation of the problem. On the other hand, for general graphs, by replacing the optimal orthogonal projection (PCA) with a randomized projection approach .