Abiy Tasissa, Rensselaer Polytechnic Institute (RPI)

Abstract

The Euclidean distance geometry (EDG) problem naturally arises in a wide variety of applications ranging from determining molecular conformations in computational chemistry to localization in sensor networks. We formulate the EDG problem as a matrix completion problem of recovering a low rank r Gram matrix with respect to certain predefined basis. The well known restricted isometry property can not apply to this formulation. Instead, we introduce a dual basis approach to theoretically analyze the proposed program. If the Gram matrix satisfies certain coherence condition, our main result shows that the underlying configuration of n points can be recovered with high probability from O(nr log2 n) uniformly random samples of the distance matrix. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different three dimensional data and protein molecules validate effectiveness and efficiency of the proposed algorithms.

Video