Extensions of classical multidimensional scaling via variable reduction (Q1855631)

This article deals with multidimensional scaling techniques for visualizing dissimilarity data, i.e., for constructing configurations of points from information about interpoint distances. The dissimilarity matrix \(\Delta\) is a symmetric square matrix with nonnegative elements whose diagonal elements are equal to zero. Given an \(n\times n\) matrix \(A=[a_{ij}]\), the \(n\times n\) matrix \(\tau(A)=[b_{ij}]\) is defined by \[ b_{ij}=-2^{-1}\left(a_{ij}-n^{-1}\sum\limits_{j=1}^{n}a_{ij}-n^{-1}\sum\limits_{i=1}^{n}a_{ij}+n^{-2}\sum\limits_{i,j=1}^{n}a_{ij}\right). \] A \(p\)-dimensional Euclidean distance matrix is an \(n\times n\) matrix \(D=[d_{ij}]\) for which there exist \(x_1,\ldots,x_{n}\in R^{p}\) such that \(d_{ij}=\|x_{i}-x_{j}\|\). Let \(\Omega_{n}\) be the set of symmetric, positive semidefinite \(n\times n\) matrices. The author considers the optimization problem: minimize \(\|\tau(\Delta)-B\|^2_{F}\), subject to \(\Delta\in C_{n},\;B\in B_{n}\), where \(\|\cdot\|_{F}\) is the Frobenius norm, \(C_{n}\) is a closed set of dissimilarity matrices, and \(B_{n}\) is a closed subset of \(\Omega_{n}\). The author introduces a certain subset \(B_{n}\subset\Omega_{n}\) and restricts attention to the case of a single dissimilarity matrix \(C_{n}={\Delta}\), and obtains an explicit global solution to the considered problem. Then for the general case an optimization strategy is proposed and the gradient projection method for finding a local solution is used. Some numerical examples with simple bound constraints are presented.