  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 this
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 different three dimensional data and protein molecules
validate effectiveness and efficiency of the proposed algorithms.
