Maximum Variance Correction

Wenlin Chen, Kilian Q. Weinberger and Yixin Chen



Maximum Variance Correction finds large-scale feasible solutions to Maximum Variance Unfolding (MVU) by post-processing embeddings from any manifold learning algorithm. It increases the scale of MVU embeddings by several orders of magnitude and is naturally parallel. This unprecedented scalability opens up new avenues of applications for manifold learning, in particular the use of MVU embeddings as effective heuristics to speed-up A* search. We demonstrate that MVC embeddings lead to un-matched reductions in search time across several non-trivial A* benchmark search problems and bridge the gap between the manifold learning literature and one of its most promising high impact applications.


MVC source code(matlab)


[1] W. Chen, K. Weinberger, and Y. Chen, Maximum Variance Correction with Application to A* Search, Proc. International Conference on Machine Learning (ICML-13), 2013. (paper)

[2] W. Chen, Y. Chen, K. Weinberger, Q. Lu, and X. Chen, Goal-Oriented Euclidean Heuristics with Manifold Learning, Proc. AAAI Conference on Artificial Intelligence (AAAI-13), 2013. (paper)

[3] Q. Lu, W. Chen, Y. Chen, K. Weinberger, and X. Chen, Utilizing Landmarks in Euclidean Heuristics for Optimal Planning, Late-Breaking Track, Proc. AAAI Conference on Artificial Intelligence (AAAI-13), 2013. (paper)


WC and YC are supported in part by NSF grants CNS-1017701 and CCF-1215302. KQW is supported by NIH grant U01 1U01NS073457-01 and NSF grants 1149882 and 1137211. The authors thank Lawrence K. Saul for many helpful discussions.

For any questions, please contact Wenlin Chen (wenlinchen AT or Yixin Chen (chen AT