The best Euclidean fit to a given distance matrix in prescribed dimensions (Q1061193)

A distance matrix is defined to be a real symmetric matrix with zero diagonal and non-positive off-diagonal entries. An \(n\times n\) distance matrix \([d_{i_ j}]\) is said to be Euclidean if there exists an integer \(k\leq n\) and points \(x_ 1,...,x_ n\in {\mathbb{R}}^ k\) such that \(d_{i_ j}=-(1/2)\| x_ i-x_ j\|^ 2\), where \(\|.\|\) is the Euclidean norm on \({\mathbb{R}}^ k\). Given a distance matrix D and a fixed \(k<n\) the author finds the closest Euclidean distance matrix to D with respect to a wide class of norms on the space of symmetric \(n\times n\) matrices. The construction uses diagonalization. It is motivated by problems of scaling and clustering of multidimensional data.