CONSTRAINED BEST EUCLIDEAN DISTANCE EMBEDDING ON A SPHERE: A MATRIX OPTIMIZATION APPROACH
CONSTRAINED BEST EUCLIDEAN DISTANCE EMBEDDING ON A SPHERE: A MATRIX OPTIMIZATION APPROACH
复制标题
球体上的约束最佳欧几里德距离嵌入：一种矩阵优化方法
DOI：
10.1137/13094918x
复制
发表时间：
2015-01-01
影响因子：
3.1
通讯作者：
Xiu, Naihua
中科院分区：
文献类型：
--
作者：
Bai, Shuanghua;Qi, Huo-Duo;Xiu, Naihua
在未知半径的球体上的数据表示问题来自各种学科，例如统计学（空间数据表示），心理学（约束多维缩放）和计算机科学（机器学习和模式识别）。最好的表示通常需要最小化球面上数据的距离函数以及满足一些欧几里得距离约束。正是这些球面和欧氏距离的限制，提出了一个巨大的挑战，现有的算法。在本文中，我们将问题转化为一个低秩约束的欧氏距离矩阵优化问题。然后，我们提出了一个迭代算法，在每一步使用二次收敛的牛顿CG方法。我们研究的基本问题，包括约束的非退化性和广义雅可比矩阵的非奇异性，以确保牛顿法的二次收敛。我们使用了一些经典的例子，从球形多维缩放，以证明该算法的灵活性，将各种约束。我们还提出了一个有趣的应用程序的圆拟合问题。
The problem of data representation on a sphere of unknown radius arises from various disciplines such as statistics (spatial data representation), psychology (constrained multidimensional scaling), and computer science (machine learning and pattern recognition). The best representation often needs to minimize a distance function of the data on a sphere as well as to satisfy some Euclidean distance constraints. It is those spherical and Euclidean distance constraints that present an enormous challenge to the existing algorithms. In this paper, we reformulate the problem as an Euclidean distance matrix optimization problem with a low rank constraint. We then propose an iterative algorithm that uses a quadratically convergent Newton-CG method at each step. We study fundamental issues including constraint nondegeneracy and the nonsingularity of generalized Jacobian that ensure the quadratic convergence of the Newton method. We use some classic examples from the spherical multidimensional scaling to demonstrate the flexibility of the algorithm in incorporating various constraints. We also present an interesting application to the circle fitting problem.