On Maximum Variance Embedding

Non-linear dimension reduction algorithms are broadly used from supervised and semi-supervised learning, to data visualization, computer vision, and manifold embedding. One such powerful technique is the Maximum Variance Unfolding (MVU), introduced by Weinberger and Saul in 2006 that remains state of the art method in some applications, e.g., unrolling a swiss roll! Separating the problem (MVU) from its popular solution, i.e., semidefinite embedding; we develop a theory for MVU and introduce new algorithms that can outperform semidefinite embedding in different scenarios, in both runtime and performance, i.e., variance of the embedding.