CONSTRAINED BEST EUCLIDEAN DISTANCE EMBEDDING ON A SPHERE: A MATRIX OPTIMIZATION APPROACH

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.