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¨om approximation of the eigenvectors and eigenvalues of a matrix. LMDS is applies the basic Nystr¨om approximation, while FastMap and MetricMap use generalizations of Nystr¨om, 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¨om 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.

PDF file

Details