FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms

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.

nystrom2.pdf
PDF file

Details

TypeInproceedings
Pages15
NumberMSR-TR-2004-26
InstitutionMicrosoft Research
> Publications > FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms