Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion. (arXiv:1804.04310v1 [cs.IT])

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well known restricted isometry property can not be satisfied in the scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $\nu$, the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nr\nu\log^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on 查看全文>>