Multigrid multidimensional scaling

Abstract

Abstract Multidimensional scaling (MDS) is a generic name for a family of algorithms that construct a configuration of points in a target metric space from information about inter‐point distances measured in some other metric space. Large‐scale MDS problems often occur in data analysis, representation and visualization. Solving such problems efficiently is of key importance in many applications. In this paper we present a multigrid framework for MDS problems. We demonstrate the performance of our algorithm on dimensionality reduction and isometric embedding problems, two classical problems requiring efficient large‐scale MDS. Simulation results show that the proposed approach significantly outperforms conventional MDS algorithms. Copyright © 2006 John Wiley & Sons, Ltd.