Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming (Q2566758): Difference between revisions

An \(n\times n\) real symmetric matrix \(D=\left[ D_{ij}\right] \) with nonnegative entries and all diagonal entries equal to \(0\) is called a ``pre-distance\ matrix''. If there exist points \(x_{1},\dots,x_{n}\in\mathbb{R}^{r}\) for some \(r\geq0\) such that \(D_{ij}=\left\| x_{i}-x_{j}\right\| _{2}^{2}\) for all \(i,j\), then \(D\) is called a ``Euclidean distance\ matrix'' \ (EDM). It is well-known that a pre-distance matrix \(D\) is an EDM if and only if \(D\) is negative semidefinite on the orthogonal complement of the vector \((1,1,\dots,1)\). The set of pre-distance matrices and the set of EDMs are convex cones in the space of all real symmetric matrices. The authors are interested in two computational problems: (NEDM) given a pre-distance matrix, find the nearest EDM in terms of the Frobenius metric (possibly with different weights in different positions in the matrix); and (EDMC) given a partial EDM with some entries unspecified, complete this matrix to a fully specified EDM. Their solution to (NEDM) is obtained by translating it into a semidefinite programming problem for which they provide a stable algorithm, especially suitable for large sparse matrices. On the other hand, they reduce (EDMC) to a problem involving a system of equations and inequalities which, under suitable conditions, reduces to a straightforward system of linear equations. They report successful solution of (EDMC) with \(n\cong10^{6}\) and about \(10^{3}\) unspecified entries. Earlier work along similar lines is found in the papers of \textit{C. R. Johnson} and \textit{P. Tarazaga} [Linear Algebra Appl. 223/224, 375--391 (1995; Zbl 0827.15032)], \textit{M. Laurent} [SIAM J. Matrix Anal. Appl. 22, 874--894 (2000; Zbl 0981.05071)] and \textit{A. Y. Alfakih, A. Khandani} and \textit{H. Wolkowicz} [Comput. Optim. Appl. 12, 13--30 (1999; Zbl 1040.90537)].