FastMap, MetricMap, and Landmark MDS are all Nyström Algorithms

Authors

John C. Platt, Knowledge Tools Group, Microsoft Research

Reference

10^th International Workshop on Artificial Intelligence and Statistics, Z. Ghahramani, R. Cowell, eds., (2005), to appear.

Abstract

This paper unifies the mathematical foundation of three multidimensional scaling algorithms: FastMap, MetricMap, and Landmark MDS (LMDS). All three algorithms are based on the Nyström approximation of the eigenvectors and eigenvalues of a matrix. LMDS is applies the basic Nyström approximation, while FastMap and MetricMap use generalizations of Nyström, including deflation and using more points to establish an embedding. Empirical experiments on the Reuters and Corel Image Features data sets show that the basic Nyström approximation outperforms these generalizations: LMDS is more accurate than FastMap and MetricMap with roughly the same computation and can become even more accurate if allowed to be slower.

Paper Link

PDF file (125K)

Earlier version appeared as Microsoft Research Technical Report MSR-TR-2004-26, (2004) : PDF file (155K)