Volume 35, Issue 4
An Inexact Smoothing Newton Method for Euclidean Distance Matrix Optimization Under Ordinal Constraints

Qingna Li & Houduo Qi

J. Comp. Math., 35 (2017), pp. 469-485.

Published online: 2017-08

Preview Full PDF 1 619
Export citation
  • Abstract

When the coordinates of a set of points are known, the pairwise Euclidean distances among the points can be easily computed. Conversely, if the Euclidean distance matrix is given, a set of coordinates for those points can be computed through the well known classical Multi-Dimensional Scaling (MDS). In this paper, we consider the case where some of the distances are far from being accurate (containing large noises or even missing). In such a situation, the order of the known distances (i.e., some distances are larger than others) is valuable information that often yields far more accurate construction of the points than just using the magnitude of the known distances. The methods making use of the order information is collectively known as nonmetric MDS. A challenging computational issue among all existing nonmetric MDS methods is that there are often a large number of ordinal constraints. In this paper, we cast this problem as a matrix optimization problem with ordinal constraints. We then adapt an existing smoothing Newton method to our matrix problem. Extensive numerical results demonstrate the efficiency of the algorithm, which can potentially handle a very large number of ordinal constraints.

  • Keywords

Nonmetric multidimensional scaling Euclidean distance embedding Ordinal constraints Smoothing Newton method

  • AMS Subject Headings

90C30 90C26 90C90.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

qnl@bit.edu.cn (Qingna Li)

hdqi@soton.ac.uk (Houduo Qi)

  • References
  • Hide All
    View All

@Article{JCM-35-469, author = {Li , Qingna and Qi , Houduo }, title = {An Inexact Smoothing Newton Method for Euclidean Distance Matrix Optimization Under Ordinal Constraints}, journal = {Journal of Computational Mathematics}, year = {2017}, volume = {35}, number = {4}, pages = {469--485}, abstract = { When the coordinates of a set of points are known, the pairwise Euclidean distances among the points can be easily computed. Conversely, if the Euclidean distance matrix is given, a set of coordinates for those points can be computed through the well known classical Multi-Dimensional Scaling (MDS). In this paper, we consider the case where some of the distances are far from being accurate (containing large noises or even missing). In such a situation, the order of the known distances (i.e., some distances are larger than others) is valuable information that often yields far more accurate construction of the points than just using the magnitude of the known distances. The methods making use of the order information is collectively known as nonmetric MDS. A challenging computational issue among all existing nonmetric MDS methods is that there are often a large number of ordinal constraints. In this paper, we cast this problem as a matrix optimization problem with ordinal constraints. We then adapt an existing smoothing Newton method to our matrix problem. Extensive numerical results demonstrate the efficiency of the algorithm, which can potentially handle a very large number of ordinal constraints.}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1702-m2016-0748}, url = {http://global-sci.org/intro/article_detail/jcm/10027.html} }
Copy to clipboard
The citation has been copied to your clipboard