A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrices
A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrices
复制标题
一种新颖的低秩矩阵补全方法，用于估计欧几里德距离矩阵中缺失的条目
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Cristiano Torezzan
中科院分区：
文献类型：
--
作者：
Nilson J. M. Moreira;L. Duarte;C. Lavor;Cristiano Torezzan
欧几里德距离矩阵（EDM）是k维欧几里德空间上的点之间的距离平方的表，在许多领域（例如工程学、大地测量学、经济学、遗传学、生物化学、心理学）中具有应用。经常出现的一个问题是缺少（或不确定）一些EDM要素。在许多情况下，只有所有成对距离的子集是可用的，并且希望有一些过程来估计缺失的距离。在本文中，我们通过低秩矩阵补全技术解决EDM中的数据缺失问题。我们利用这样的事实，即EDM的秩至多为k+2，并且不依赖于点的数量，而点的数量通常比k大得多。我们使用奇异值分解方法，该方法考虑要完成的矩阵的秩，并在每次迭代中计算控制方法收敛的参数。在进行了大量的计算实验后，我们可以观察到，我们的建议能够在几分钟内以高精度恢复超过1000个点的随机EDM和高达98%的丢失数据。此外，与其他竞争性最先进的技术相比，我们的方法需要较少的迭代次数。
A Euclidean Distance Matrix (EDM) is a table of distance-square between points on a k- dimensional Euclidean space, with applications in many fields (e.g. engineering, geodesy, economics, genetics, biochemistry, psychology). A problem that often arises is the absence (or uncertainty) of some EDM elements. In many situations, only a subset of all pairwise distances is available and it is desired to have some procedure to estimate the missing distances. In this paper, we address the problem of missing data in EDM through low-rank matrix completion techniques. We exploit the fact that the rank of a EDM is at most k+2 and does not depend on the number of points, which is, in general, much bigger then k. We use a Singular Value Decomposition approach that considers the rank of the matrix to be completed and computes, in each iteration, a parameter that controls the convergence of the method. After performing a number of computational experiments, we could observe that our proposal was able to recover, with high precision, random EDMs with more than one thousand points and up to 98 percent of missing data in few minutes. Additionally, our method required a smaller number of iterations when compared to other competitive state-of-art technique.