Adaptive Interpolation of Multidimensional Scaling

The recent explosion of publicly available biology gene sequences and chemical compounds offers an unprece-dented opportunity for data mining. To make data analysis feasible for such vast volume and high-dimensional scientific data, we apply high performance dimension reduction algorithms. It facilitates the investigation of unknown structures in a three dimensional visualization. Among the known dimension reduction algorithms, we utilize the multidimensional scaling (MDS) algorithm to configure the given high-dimensional or abstract data into a target di-mension. However, the MDS algorithm requires large physical memory as well as computational resources. In order to reduce computational complexity and memory requirement effectively, the interpolation method of the MDS was proposed in 2010. With minor trade-off of approximation, the MDS interpolation method enables us to process mil-lions of data points with modest amounts of computation and memory requirement. In this paper, we would like to improve the mapping quality of the MDS interpolation approach by adapting the original dissimilarity based on the ratio between the original dissimilarity and the corresponding mapping distances. Our experimental results illustrate that the quality of interpolated mapping results are improved by adding the adaptation step without runtime loss com-pared to the original interpolation method. With the proposed adaptive interpolation method, we construct a better configuration of millions of out-of-sample data into a target dimension than the previous interpolation method.