A Convex Matrix Optimization for the Additive Constant Problem in Multidimensional Scaling with Application to Locally Linear Embedding
将多维缩放中的加常数问题重新表述为近半负定矩阵的凸优化，以最小化原始距离的扭曲，并开发牛顿共轭梯度法，证明二次收敛，同时应用于局部线性嵌入处理缺失值问题。
The additive constant problem has a long history in multidimensional scaling and it has recently been used to resolve the issue of indefiniteness of the geodesic distance matrix in ISOMAP. But it would lead to a large positive constant being added to all eigenvalues of the centered geodesic distance matrix, often causing significant distortion of the original distances. In this paper, we reformulate the problem as a convex optimization of almost negative semidefinite matrix so as to achieve minimal variation of the original distances. We then develop a Newton-CG method and further prove its quadratic convergence. Finally, we include a novel application to the famous LLE (locally linear embedding in nonlinear dimensionality reduction), addressing the issue when the input of LLE has missing values. We justify the use of the developed method to tackle this issue by establishing that the local Gram matrix used in LLE can be obtained through a local Euclidean distance matrix. The effectiveness of our method is demonstrated by numerical experiments.