基于矩阵填充原理重建欧式距离矩阵

欧式距离矩阵（EDM）在各领域的应用日益深入，而实际中多数EDM矩阵元素受噪声污染或者丢失，本文提出从有限的信息中重建EDM，实现矩阵填充的方法。利用基于凸优化的固定点迭代算法，采用Matlab语言编程，选取合适参数，经多次迭代使运行程序收敛，得出的重建矩阵效果显著。

【关键词】欧式距离矩阵 矩阵填充 奇异值分解 低秩

近年来EDM重建问题得到许多学者的关注和研究，它主要应用于机器学习，多维尺度分析，核磁共振分子构象等方面。根据给定的几个成对节点间的距离如何有效地重建低维几何结构的节点？这就是欧氏距离矩阵填充所要解决的问题。本文利用低维空间节点距离矩阵的低秩性，将缺少的数据元素进行有效重建，得到准确、结构性良好的欧式距离矩阵（EDM）。

1 相关理论

1.1 欧式距离矩阵

2 数值结果

本文提出固定点迭代（FPC）算法重建目标矩阵DM，为解决欧式距离矩阵填充问题提供了一个有效方案。该算法主要用来实现秩最小化矩阵填充问题，通过选择适当参数，运行程序用Matlab语言编写，重建效果显著。

评估EDM重建准确率的一个重要参数为相对误差，而采用FPC算法实现重建的目标欧式距离矩阵，其相对误差量级均在10-4，已然是非常准确的重构结果。如图1、2所示，选取DM是一组秩为5，维数不同的欧式距离矩阵。从图1知，矩阵维数越大，最小采样率值越小，即仅需采集非常少量的数据便可准确的重建EDM；图2中随着程序运行时间随着维数的增大而增长。这说明采样FPC算法重建欧式距离矩阵，在采样率、运行时间及精准度方面均具有优越性，尤其在重建低秩大型矩阵上采样数目极少且运行速率较快。

3 结论

本文利用FPC算法将程序收敛到秩最小化来解决部分欧式距离矩阵重建问题。但是由于待重建的目标矩阵是未知的，那么要想得到准确的重建效果，就需要分析观测元素数量，质点坐标分布结构等问题。大多数EDM在许多方面均有广泛应用，并且矩阵元间有很大的相关性，则如何利用这一特性更准确地实现矩阵重建对距离估算问题的研究具有积极意义。

参考文献

[1]A.Y.Alfakih，A.Khandani，H.Wolkowcz.Solving Euclidean distance matrix completion problems via semidefinite programming[J]， Computational Optimization and Applications，1999，12（1）：13-30.

[2]Ivan Dokmanic，Reza Parhizkar，Juri Ranieri，Martin Vetterli.Euclidean distance matrices essential theory， algorithms and applications[J]， IEEE Signal Processing Magazine，ISSN：1053-5888.

[3]郑宝东.线性代数与空间解析几何[M].北京：高等教育出版社，2003：60-61.

作者简介

韦仙（1988-），女，现为太原工业学院理学系硕士在读学生。主要研究方向为压缩感知与矩阵填充。

作者单位

太原工业学院理学系 山西省太原市 030008