Title: Robust Euclidean Embedding via EDM Optimization

Abstract: This paper aims to propose an efficient numerical method for the most challenging problem
known as the robust Euclidean embedding (REE) in the family of multi-dimensional scaling (MDS).
The problem is notoriously known to be nonsmooth, nonconvex and its objective is non-Lipschitzian.

We first explain that the semidefinite programming (SDP) relaxations and Euclidean distance matrix
(EDM) approach, popular for other types of problems in the MDS family,
failed to provide a viable method for this problem.

We then propose a penalized REE (PREE), which can be economically majorized.
We show that the majorized problem is convex provided that the penalty parameter is above certain
threshold.

Moreover, it has a closed-form solution, resulting in an efficient algorithm dubbed as
PREEEDM (for Penalized REE via EDM optimization).
We will prove among others that PREEEDM converges to a stationary point of PREE.

Finally, the efficiency of PREEEDM will be compared with several state-of-the-art methods including SDP and EDM solvers on a large number of test problems from sensor network localization and molecular conformation.

This is based on a joint work with Shenglong Zhou and Naihua Xiu.