Back to search

University of Southampton

Majorization-projection methods for multidimensional scaling via Euclidean distance matrix optimization

Abstract

dc:description.abstract

This thesis aims to propose an efficient numerical method for a historically popular problem, multi-dimensional scaling (MDS), through the Euclidean distance matrix (EDM) optimization. The problem tries to locate a number of points in a low dimensional real space based on some inter-vector dissimilarities (i.e., noise contaminated Euclidean distances), which has been notoriously known to be non-smooth and non-convex.<br/><br/>When it comes to solving the problem, four classes of stress based minimizations have been investigated. They are stress minimization, squared stress minimization, robust MDS and robust Euclidean embedding, yielding numerous methods that can be summarized into three representative groups: coordinates descent minimization, semi-definite programming (SDP) relaxation and EDM optimization. Each of these methods was cast based on only one or two minimizations and difficult to process the rest. Especially, no efficient methods have been proposed to address the robust Euclidean embedding to the best of our knowledge.<br/><br/>In this thesis, we manage to formulate the problem into a general EDM optimization model with ability to possess four objective functions that respectively correspond to above mentioned four minimizations. Instead of concentrating on the primary model, we take its penalization into consideration but also reveal their relation later on. The appealing feature of the penalization allows its four objective functions to be economically majorized by convex functions provided that the penalty parameter is above certain threshold. Then the projection of the unique solution of the convex majorization onto a box set enjoys a closed form, leading to an extraordinarily efficient algorithm dubbed as MPEDM, an abbreviation for Majorization-Projection via EDM optimization. We prove that MPEDM involving four objective functions converges to a stationary point of the penalization and also an -KKT point of the primary problem. Therefore, we succeed in achieving a viable method that is able to solve all four stress based minimizations.<br/><br/>Finally, we conduct extensive numerical experiments to see the performance of MPEDM by carrying out self-comparison under four objective functions. What is more, when it is against with several state-of-the-art methods on a large number of test problems including wireless sensor network localization and molecular conformation, the superiorly fast computational speed and very desirable accuracy highlight that it will become a very competitive embedding method in high dimensional data setting.<br/>

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhou, Shenglong
Advisor dc:contributor.advisor
  • Qi, Hou-Duo

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

Zhou, Shenglong. Majorization-projection methods for multidimensional scaling via Euclidean distance matrix optimization. doctoral thesis, University of Southampton, 2018.