Back to search

University of Southampton

Numerical methods for constrained Euclidean distance matrix optimization

Abstract

dc:description.abstract

This thesis is an accumulation of work regarding a class of constrained Euclidean Distance Matrix (EDM) based optimization models and corresponding numerical approaches. EDM-based optimization is powerful for processing distance information which appears in diverse applications arising from a wide range of fields, from which the motivation for this work comes. Those problems usually involve minimizing the error of distance measurements as well as satisfying some Euclidean distance constraints, which may present enormous challenge to the existing algorithms. In this thesis, we focus on problems with two different types of constraints. The first one consists of spherical constraints which comes from spherical data representation and the other one has a large number of bound constraints which comes from wireless sensor network localization.<br/><br/>For spherical data representation, we reformulate the problem as an Euclidean distance matrix optimization problem with a low rank constraint. We then propose an iterative algorithm that uses a quadratically convergent Newton-CG method at its each step. We study fundamental issues including constraint nondegeneracy and the nonsingularity of generalized Jacobian that ensure the quadratic convergence of the Newton method. We use some classic examples from the spherical multidimensional scaling to demonstrate the flexibility of the algorithm in incorporating various constraints.<br/><br/>For wireless sensor network localization, we set up a convex optimization model using EDM which integrates connectivity information as lower and upper bounds on the elements of EDM, resulting in an EDM-based localization scheme that possesses both efficiency and robustness in dealing with flip ambiguity under the presence of high level of noises in distance measurements and irregular topology of the concerning network of moderate size.<br/><br/>To localize a large-scale network efficiently, we propose a patching-stitching localization scheme which divides the network into several sub-networks, localizes each sub-network separately and stitching all the sub-networks together to get the recovered network. Mechanism for separating the network is discussed. EDM-based optimization model can be extended to add more constraints, resulting in a flexible localization scheme for various kinds of applications. Numerical results show that the proposed algorithm is promising.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bai, Shuanghua
Advisors dc:contributor.advisor
  • Qi, Hou-Duo
  • Nguyen, Tri-Dung
  • Xu, Huifu
ORCID person:identifier.orcid

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Bai, Shuanghua. Numerical methods for constrained Euclidean distance matrix optimization. doctoral thesis, University of Southampton, 2016.