Data visualization by multidimensional scaling: a deterministic annealing approach

Multidimensional scaling addresses the problem how proximity data can be fa ithfully visualized as points in a low-dimensional Euclidean space. The qua lity of a data embedding is measured by a stress function which compares pr oximity values with Euclidean distances of the respective points. The corre sponding minimization problem is non-convex and sensitive to local minima. We present a novel deterministic annealing algorithm for the frequently use d objective SSTRESS and for Sammon mapping, derived in the framework of max imum entropy estimation. Experimental results demonstrate the superiority o f our optimization technique compared to conventional gradient descent meth ods. (C) 2000 Published by Elsevier Science Ltd. All rights reserved.