Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming

Suliman Al-Homidan; Henry Wolkowicz

doi:10.1016/j.laa.2005.03.021

Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming

Suliman Al-Homidan
, Henry Wolkowicz^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

38 Scopus citations

Abstract

A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free. The Euclidean distance matrix completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) Euclidean distance matrix problem is to find a Euclidean distance matrix, EDM, that is nearest in the Frobenius norm to the matrix A, when the free variables are discounted. In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant. We briefly discuss numerical tests.

Original language	English
Pages (from-to)	109-141
Number of pages	33
Journal	Linear Algebra and Its Applications
Volume	406
Issue number	1-3
DOIs	https://doi.org/10.1016/j.laa.2005.03.021
State	Published - 1 Sep 2005
Externally published	Yes

Bibliographical note

Funding Information:
∗ Corresponding author. Tel.: +1 519 888 4567x5589. E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (H. Wol-kowicz). URL: http://orion.math.uwaterloo.ca/∼hwolkowi/henry/reports/ABSTRACTS.html 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia. 2 Research supported by The Natural Sciences and Engineering Research Council of Canada.

Keywords

Completion problems
Euclidean distance matrix
Large sparse problems
Nearest matrix approximation
Semidefinite programming

ASJC Scopus subject areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2005.03.021

Cite this

@article{5263fe0237794aa3a7f4521a0833425b,

title = "Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming",

abstract = "A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free. The Euclidean distance matrix completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) Euclidean distance matrix problem is to find a Euclidean distance matrix, EDM, that is nearest in the Frobenius norm to the matrix A, when the free variables are discounted. In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant. We briefly discuss numerical tests.",

keywords = "Completion problems, Euclidean distance matrix, Large sparse problems, Nearest matrix approximation, Semidefinite programming",

author = "Suliman Al-Homidan and Henry Wolkowicz",

note = "Funding Information: ∗ Corresponding author. Tel.: +1 519 888 4567x5589. E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (H. Wol-kowicz). URL: http://orion.math.uwaterloo.ca/∼hwolkowi/henry/reports/ABSTRACTS.html 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia. 2 Research supported by The Natural Sciences and Engineering Research Council of Canada.",

year = "2005",

month = sep,

day = "1",

doi = "10.1016/j.laa.2005.03.021",

language = "English",

volume = "406",

pages = "109--141",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "1-3",

}

TY - JOUR

T1 - Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming

AU - Al-Homidan, Suliman

AU - Wolkowicz, Henry

N1 - Funding Information: ∗ Corresponding author. Tel.: +1 519 888 4567x5589. E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (H. Wol-kowicz). URL: http://orion.math.uwaterloo.ca/∼hwolkowi/henry/reports/ABSTRACTS.html 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia. 2 Research supported by The Natural Sciences and Engineering Research Council of Canada.

PY - 2005/9/1

Y1 - 2005/9/1

N2 - A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free. The Euclidean distance matrix completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) Euclidean distance matrix problem is to find a Euclidean distance matrix, EDM, that is nearest in the Frobenius norm to the matrix A, when the free variables are discounted. In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant. We briefly discuss numerical tests.

AB - A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free. The Euclidean distance matrix completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) Euclidean distance matrix problem is to find a Euclidean distance matrix, EDM, that is nearest in the Frobenius norm to the matrix A, when the free variables are discounted. In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant. We briefly discuss numerical tests.

KW - Completion problems

KW - Euclidean distance matrix

KW - Large sparse problems

KW - Nearest matrix approximation

KW - Semidefinite programming

UR - https://www.scopus.com/pages/publications/23044487729

U2 - 10.1016/j.laa.2005.03.021

DO - 10.1016/j.laa.2005.03.021

M3 - Article

AN - SCOPUS:23044487729

SN - 0024-3795

VL - 406

SP - 109

EP - 141

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 1-3

ER -

Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this