Return to search

Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion

The main result of this thesis is the development of a theory of semidefinite facial reduction for the Euclidean distance matrix completion problem. Our key result shows a close connection between cliques in the graph of the partial Euclidean distance matrix and faces of the semidefinite cone containing the feasible set of the semidefinite relaxation. We show how using semidefinite facial reduction allows us to dramatically reduce the number of variables and constraints required to represent the semidefinite feasible set. We have used this theory to develop a highly efficient algorithm capable of solving many very large Euclidean distance matrix completion problems exactly, without the need for a semidefinite optimization solver. For problems with a low level of noise, our SNLSDPclique algorithm outperforms existing algorithms in terms of both CPU time and accuracy. Using only a laptop, problems of size up to 40,000 nodes can be solved in under a minute and problems with 100,000 nodes require only a few minutes to solve.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5093
Date January 2010
CreatorsKrislock, Nathan
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0021 seconds