An Inexact Smoothing Newton Method for Euclidean Distance Matrix Optimization Under Ordinal Constraints
Year: 2017
Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 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 are 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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1702-m2016-0748
Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 469–485
Published online: 2017-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 17
Keywords: Nonmetric multidimensional scaling Euclidean distance embedding Ordinal constraints Smoothing Newton method.
Author Details
-
Ordinal Distance Metric Learning with MDS for Image Ranking
Yu, Panpan | Li, QingnaAsia-Pacific Journal of Operational Research, Vol. 35 (2018), Iss. 01 P.1850007
https://doi.org/10.1142/S0217595918500070 [Citations: 2] -
Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints
Lu, Si-Tong | Zhang, Miao | Li, Qing-NaComputational Optimization and Applications, Vol. 76 (2020), Iss. 2 P.535
https://doi.org/10.1007/s10589-020-00189-9 [Citations: 4] -
An Ordinal Weighted EDM Model for Nonmetric Multidimensional Scaling
Li, Qing-Na | Zhang, Chi | Cao, MengzhiAsia-Pacific Journal of Operational Research, Vol. 39 (2022), Iss. 03
https://doi.org/10.1142/S0217595921500330 [Citations: 1]