Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion

Euclidean distance matrices;low-rank matrix completion;semidefinite relaxations;facial reduction;wireless sensor network localization;molecular conformation;Combinatorics and Optimization

Krislock, Nathan

University of Waterloo

关键词: Euclidean distance matrices;    low-rank matrix completion;    semidefinite relaxations;    facial reduction;    wireless sensor network localization;    molecular conformation;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5093/1/Krislock_Nathan.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.