Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming (Q2566758): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 08:36, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming |
scientific article |
Statements
Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming (English)
0 references
28 September 2005
0 references
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)].
0 references
Euclidean distance matrix
0 references
completion problem
0 references
semidefinite programming
0 references
nearest matrix approximation
0 references
large sparse problems
0 references