Premium
Multigrid multidimensional scaling
Author(s) -
Bronstein M. M.,
Bronstein A. M.,
Kimmel R.,
Yavneh I.
Publication year - 2006
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.475
Subject(s) - multidimensional scaling , multigrid method , embedding , scaling , metric (unit) , dimensionality reduction , mathematics , representation (politics) , curse of dimensionality , scale (ratio) , visualization , space (punctuation) , computer science , point (geometry) , algorithm , theoretical computer science , data mining , artificial intelligence , partial differential equation , geometry , mathematical analysis , statistics , operations management , physics , quantum mechanics , politics , political science , law , economics , operating system
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.