AN INEXACT SMOOTHING NEWTON METHOD FOR EUCLIDEAN DISTANCE MATRIX OPTIMIZATION UNDER ORDINAL CONSTRAINTS

• 来源期刊: 计算数学（英文版）
• 关键词: Nonmetric multidimensional scaling Euclidean distance embedding Ordinal constraints Smoothing Newton method
• 年，卷（期）: 2017,（4）
• 页码范围: 469-485
• 页数: 17页
• 语种: 英文
• DOI: 10.4208/jcm.1702-m2016-0748

摘要

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.