« search calendars« DIMACS Workshop on Optimization in Distance Geometry

« A Matrix Completion Framework for the Euclidean Distance Geometry Problem

A Matrix Completion Framework for the Euclidean Distance Geometry Problem

June 26, 2019, 10:40 AM - 11:20 AM



Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.

Abiy Tasissa, Rensselaer Polytechnic Institute (RPI)

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.