Landmark MDS ensemble

Abstract

Landmark multidimensional scaling (LMDS) uses a subset of data (landmark points) to solve classical multidimensional scaling (MDS), where the scalability is increased but the approximation is noise-sensitive. In this paper we present an LMDS ensemble where we use a portion of the input in a piecewise manner to solve classical MDS, combining individual LMDS solutions which operate on different partitions of the input. Ground control points (GCPs) that are shared by partitions considered in the ensemble, allow us to align individual LMDS solutions in a common coordinate system through affine transformations. We incorporate priors into combining multiple LMDS solutions such that the weighted averaging by priors improves the noise-robustness of our method. Our LMDS ensemble is much less noise-sensitive while maintaining the scalability and the speed of LMDS. Experiments on synthetic data (noisy grid) and real-world data (similar image retrieval) confirm the high performance of the proposed LMDS ensemble. (C) 2009 Elsevier Ltd. All rights reserved.